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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Food Buckets to Feed the Hamsters

Number: 2191

Difficulty: Medium

Paid? No

Companies: Microsoft, Sprinklr, Grab

Problem Description

You are given a 0-indexed string hamsters where hamsters[i] is either 'H' (indicating there is a hamster at index i) or '.' (indicating an empty index). You must place food buckets at some empty indices so that every hamster can be fed. A hamster is fed if there is at least one food bucket immediately to its left or right. Return the minimum number of buckets you need to place, or -1 if it is impossible to feed all hamsters.

Key Insights

  • Use a greedy approach to place buckets in a way that can potentially feed more than one hamster.
  • Prioritize placing a bucket at the right neighbor of a hamster if possible, since it may also cover a hamster further to the right.
  • Always check if a hamster is already fed by a bucket placed to its left before trying to add a new bucket.
  • If a hamster has neither neighbor available for bucket placement, the answer is -1.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1) extra space if using the input string converted to a mutable array.

Solution

The main idea is to iterate over the string and for every hamster:

  1. If its left neighbor already has a bucket, continue.
  2. Otherwise, if its right neighbor is available (i.e., an empty cell '.'), place a bucket there.
  3. If the right neighbor is not available but the left neighbor is (and hasn’t been used already), place a bucket there.
  4. If neither neighbor can be used, return -1 since that hamster cannot be fed. We mark the placed buckets by modifying the array (or string) to denote positions where buckets have been placed. This ensures that subsequent hamsters can recognize if they are already fed by a neighboring bucket.

Code Solutions

# Python solution with line-by-line comments

def minimumBuckets(hamsters: str) -> int:
    n = len(hamsters)
    # Convert string to a list for easy modification (mark bucket placements)
    hamList = list(hamsters)
    count = 0

    for i in range(n):
        # Process only if the current index has a hamster
        if hamList[i] == 'H':
            # If the left neighbor already has a bucket, the hamster is fed.
            if i - 1 >= 0 and hamList[i - 1] == 'B':
                continue
            # Try placing a bucket at the right neighbor if it's empty.
            if i + 1 < n and hamList[i + 1] == '.':
                hamList[i + 1] = 'B'
                count += 1
            # Otherwise, check if the left neighbor is available.
            elif i - 1 >= 0 and hamList[i - 1] == '.':
                hamList[i - 1] = 'B'
                count += 1
            else:
                # If neither neighbor can be used, it's impossible to feed this hamster.
                return -1
    return count

# Example usage:
print(minimumBuckets("H..H"))    # Expected output: 2
print(minimumBuckets(".H.H."))   # Expected output: 1
print(minimumBuckets(".HHH."))   # Expected output: -1
← Back to All Questions