We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Food Buckets to Feed the Hamsters

Difficulty: Medium

Problem Description

You are given a 0-indexed string hamsters where hamsters[i] is either 'H' indicating that there is a hamster at index i, or '.' indicating that index i is empty. You will add some number of food buckets at the empty indices in order to feed the hamsters. A hamster can be fed if there is at least one food bucket to its left or to its right. Return the minimum number of food buckets you should place at empty indices to feed all the hamsters or -1 if it is impossible to feed all of them.

Key Insights

  • Hamsters need food buckets at adjacent indices (left or right) to be fed.
  • We can place food buckets optimally to minimize their number while ensuring all hamsters are fed.
  • If two hamsters are adjacent (e.g., "HH"), it is impossible to feed them if there are no empty spots between them.
  • The greedy approach works by placing food buckets in the most efficient way possible, usually prioritizing the furthest empty spots that can feed the maximum number of hamsters.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution can be approached using a greedy algorithm. We can iterate through the string hamsters and whenever we encounter a hamster ('H'), we check the adjacent positions to place food buckets. If the adjacent positions are empty ('.'), we place a bucket in such a way that it can help feed the maximum number of hamsters. If we find a situation where hamsters cannot be fed (like consecutive 'H's without empty spots in between), we return -1.

Code Solutions

def minFoodBuckets(hamsters: str) -> int:
    n = len(hamsters)
    buckets = 0
    i = 0

    while i < n:
        if hamsters[i] == 'H':
            # Check if we can place a bucket to the left or right
            if i > 0 and hamsters[i - 1] == '.':
                buckets += 1
                i += 1  # Skip the next index since we placed a bucket
            elif i < n - 1 and hamsters[i + 1] == '.':
                buckets += 1
                i += 2  # Skip the next index since we placed a bucket
            else:
                return -1  # Impossible to feed this hamster
        else:
            i += 1

    return buckets
← Back to All Questions