Minimum Number of Food Buckets to Feed the Hamsters

Med

#1898Time: O(N), where N is the length of the input string. We perform a single pass through the array.Space: O(N), where N is the length of the input string. This is due to the creation of a character array to store the state of buckets.3 companies

Patterns

Dynamic Programming Greedy

Data structures

String

Companies

Grab Sprinklr Geico

Prompt

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. More formally, a hamster at index i can be fed if you place a food bucket at index i - 1 and/or at index i + 1.

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.

Example 1:

Input: hamsters = "H..H"
Output: 2
Explanation: We place two food buckets at indices 1 and 2.
It can be shown that if we place only one food bucket, one of the hamsters will not be fed.

Example 2:

Input: hamsters = ".H.H."
Output: 1
Explanation: We place one food bucket at index 2.

Example 3:

Input: hamsters = ".HHH."
Output: -1
Explanation: If we place a food bucket at every empty index as shown, the hamster at index 2 will not be able to eat.

Constraints:

1 <= hamsters.length <= 10⁵
hamsters[i] is either'H' or '.'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach employs a greedy strategy by iterating through the hamsters and placing buckets as needed. To keep track of where buckets are placed and which hamsters are consequently fed, it uses an auxiliary character array. This makes the logic for checking the status of adjacent spots straightforward but comes at the cost of additional memory.

Algorithm

Convert the input string hamsters into a character array chars to allow for modification.
Initialize a counter for buckets, buckets = 0.
Iterate through the character array from left to right with an index i.
If chars[i] is a hamster ('H'):
- First, check if this hamster has already been fed by a bucket placed to its left. This would be the case if i > 0 and chars[i-1] has been marked as a bucket (e.g., 'B'). If so, continue to the next position.
- If the hamster is not fed, we must place a bucket. The greedy choice is to place it to the right. If i + 1 is a valid index and chars[i + 1] is an empty spot ('.'), increment buckets and update chars[i + 1] to 'B' to mark that a bucket has been placed.
- If placing a bucket on the right is not possible, we must try to place it on the left. If i - 1 is a valid index and chars[i - 1] is an empty spot ('.'), increment buckets and update chars[i - 1] to 'B'.
- If neither the left nor the right side has an empty spot, it's impossible to feed this hamster. Return -1.
After the loop completes, return the total buckets count.

Walkthrough

The core idea is to make a local optimal choice at each step, which leads to a global optimum. We iterate from left to right. When we encounter a hamster 'H', we first check if a bucket placed for a previous hamster already feeds it. If not, we need to place a new bucket. The best greedy move is to place the bucket to the right of the current hamster (at index i+1) if possible. This is because a bucket at i+1 not only feeds the hamster at i but also has the potential to feed a future hamster at i+2, maximizing its utility. If we cannot place a bucket to the right, our only other option is to place it to the left (at i-1). If neither spot is available, the task is impossible. We use a character array, a copy of the input string, to mark the locations of placed buckets (e.g., with a 'B'), which simplifies state tracking.

1class Solution {2    public int minimumBuckets(String hamsters) {3        char[] chars = hamsters.toCharArray();4        int n = chars.length;5        int buckets = 0;6        for (int i = 0; i < n; i++) {7            if (chars[i] == 'H') {8                // Check if already fed by a bucket on the left9                if (i > 0 && chars[i - 1] == 'B') {10                    continue;11                }12 13                // Try to place a bucket to the right (greedy choice)14                if (i + 1 < n && chars[i + 1] == '.') {15                    buckets++;16                    chars[i + 1] = 'B'; // Mark the bucket17                } 18                // Else, try to place a bucket to the left19                else if (i - 1 >= 0 && chars[i - 1] == '.') {20                    buckets++;21                    chars[i - 1] = 'B'; // Mark the bucket22                } 23                // Impossible to feed this hamster24                else {25                    return -1;26                }27            }28        }29        return buckets;30    }31}

Complexity

Time

O(N), where N is the length of the input string. We perform a single pass through the array.

Space

O(N), where N is the length of the input string. This is due to the creation of a character array to store the state of buckets.

Trade-offs

Pros

The logic is very explicit and easy to reason about, as the state of placed buckets is clearly maintained in the auxiliary array.

Cons

Requires extra space proportional to the length of the input string, which can be significant for large inputs.

This is the most efficient approach, solving the problem in a single pass with constant extra space. It uses the same greedy principle as the previous method but avoids the O(N) space complexity by cleverly manipulating the loop index instead of using an auxiliary array to track state. The core idea remains: when feeding a hamster, always prioritize placing a bucket to its right to maximize its coverage.

Algorithm

Initialize a counter for buckets, buckets = 0.
Iterate through the hamsters string using an index i from 0 to n-1.
If the character at i is a hamster ('H'):
- We apply our greedy strategy. First, check if we can place a bucket to the right. If i + 1 is within bounds and hamsters.charAt(i + 1) is an empty spot ('.'), this is the optimal move. Increment buckets and advance the loop index i by 2. This jump is crucial: it skips over the position where the bucket was placed (i+1) and the next position (i+2), as any hamster there would be fed by this new bucket.
- If placing a bucket to the right is not possible, we check the left. If i - 1 is within bounds and hamsters.charAt(i - 1) is an empty spot ('.'), we must place a bucket there. Increment buckets. No index jump is needed here.
- If neither the right nor the left spot is available for a bucket, it's impossible to feed the hamster. Return -1.
If the character at i is an empty spot ('.'), we simply let the loop increment i to move to the next position.
After the loop finishes, return the total buckets count.

Walkthrough

This optimized solution refines the greedy strategy to work in-place without needing an extra array. We iterate through the string, and upon finding a hamster at index i, we decide where to place a bucket. The best choice is always i+1 if it's empty. By placing a bucket at i+1, we feed the hamster at i and potentially one at i+2. The key insight is that we can account for this by skipping the next two indices in our loop. We do this by advancing i by 2. The loop's own increment will then take over, effectively moving our focus to i+3. This prevents double-counting buckets or re-evaluating an already-fed hamster. If i+1 is not a valid spot, we check i-1. Since we are iterating left-to-right, checking hamsters.charAt(i-1) is sufficient; we don't need to worry about whether a bucket was already placed there, because our i+=2 jump logic would have skipped over i if a bucket at i-1 had been placed for a hamster at i-2. This makes the logic work with O(1) space.

1class Solution {2    public int minimumBuckets(String hamsters) {3        int n = hamsters.length();4        int buckets = 0;5        for (int i = 0; i < n; ++i) {6            if (hamsters.charAt(i) == 'H') {7                // Try to place a bucket to the right (greedy choice)8                if (i + 1 < n && hamsters.charAt(i + 1) == '.') {9                    buckets++;10                    // This bucket covers hamsters at i and i+2.11                    // Skip the next two positions.12                    i += 2;13                } 14                // Else, try to place a bucket to the left15                else if (i - 1 >= 0 && hamsters.charAt(i - 1) == '.') {16                    buckets++;17                } 18                // Impossible to feed this hamster19                else {20                    return -1;21                }22            }23        }24        return buckets;25    }26}

Complexity

Time

O(N), where N is the length of the input string. Although we sometimes jump the index, we still visit each character at most a constant number of times.

Space

O(1). We only use a few variables to store the count and the loop index, which does not depend on the input size.

Trade-offs

Pros

Extremely efficient in terms of memory, using only a constant amount of extra space.
Achieves the optimal time complexity with a single pass.

Cons

The logic involving the loop index jump (i += 2) can be slightly less intuitive to understand at first glance compared to explicitly marking buckets in an array.

Solutions

Solution

1class Solution { public int minimumBuckets ( String street ) { int n = street . length (); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( street . charAt ( i ) == 'H' ) { if ( i + 1 < n && street . charAt ( i + 1 ) == '.' ) { ++ ans ; i += 2 ; } else if ( i > 0 && street . charAt ( i - 1 ) == '.' ) { ++ ans ; } else { return - 1 ; } } } return ans ; } }

1class Solution {2public:3  int minimumBuckets(string street) {4    int n = street.size();5    int ans = 0;6    for (int i = 0; i < n; ++i) {7      if (street[i] == 'H') {8        if (i + 1 < n && street[i + 1] == '.') {9          ++ans;10          i += 2;11        } else if (i && street[i - 1] == '.') {12          ++ans;13        } else {14          return -1;15        }16      }17    }18    return ans;19  }20};

1class Solution : def minimumBuckets ( self , street : str ) -> int : ans = 0 i , n = 0 , len ( street ) while i < n : if street [ i ] == 'H' : if i + 1 < n and street [ i + 1 ] == '.' : i += 2 ans += 1 elif i and street [ i - 1 ] == '.' : ans += 1 else : return - 1 i += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem