Minimum Number of Food Buckets to Feed the Hamsters - Solution & Explanation
Problem Statement
You are given a 0-indexed string hamsters where hamsters[i] is either:
'H'indicating that there is a hamster at indexi, or'.'indicating that indexiis 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 <= 105hamsters[i]is either'H'or'.'.
Approach Overview
Problem Overview: You receive a street represented as a string where 'H' is a hamster house and '.' is an empty spot. A food bucket placed on '.' can feed adjacent hamsters (left or right). The goal is to place the minimum number of buckets so every hamster has at least one adjacent bucket. If any hamster cannot be fed, return -1.
Approach 1: Greedy Placement (O(n) time, O(1) space)
This problem works well with a greedy strategy. Iterate through the street from left to right. When you encounter a hamster, try to place a bucket to its right first if the spot is empty. That bucket can potentially serve both the current hamster and the next one, which minimizes total buckets. If the right side is unavailable, check the left side. If neither side has an empty position, feeding this hamster is impossible and the answer is -1. The key insight: placing the bucket on the right side whenever possible maximizes sharing between neighboring hamsters.
During iteration, mark the bucket placement logically and continue scanning. Because each character is processed once and bucket placement decisions are local, the algorithm runs in linear time with constant extra memory. This is the most common interview solution because it balances correctness with simplicity.
Approach 2: Two-Pass Strategy (O(n) time, O(n) space)
A structured alternative uses two passes over the string. In the first pass, handle hamsters that must place a bucket on a specific side (for example, when only one adjacent spot is available). Record placements in an auxiliary array representing bucket positions. In the second pass, process remaining hamsters and place buckets where they can serve multiple houses efficiently. This staged decision process avoids conflicts where multiple hamsters compete for the same location.
This approach resembles techniques used in dynamic programming-style constraint handling, where earlier decisions influence later placements. While the complexity is still linear, it uses extra memory to track bucket states and is slightly more verbose than the greedy solution. The advantage is clearer separation between forced placements and optimal placements.
Recommended for interviews: The greedy approach is the expected solution. Interviewers want to see whether you recognize the local optimal rule: prioritize placing buckets to the right of each hamster to allow sharing with the next house. Discussing the two-pass strategy shows you understand constraint handling, but implementing the greedy single-pass solution demonstrates stronger problem-solving intuition and leads directly to the optimal O(n) time and O(1) space solution.
Approach 1: Greedy Approach
In this approach, we'll iterate through the string and place buckets at appropriate indices to minimize the total number of buckets while ensuring all hamsters are fed. We'll attempt to place a bucket to the hamster's right first, as it can potentially serve future hamsters on the right, promoting efficiency.
This C solution iterates through the 'hamsters' string. For each hamster 'H', it tries to place a food bucket to its right (as `i + 1`) if possible. If not, it looks to place it to its left (as `i - 1`). If neither is possible, it returns -1 indicating it's impossible to feed all hamsters. Otherwise, it counts the buckets used and reports the total.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), using only a few extra variables for counting.
Approach 2: Two-Pass Strategy
This approach entails two traversals of the string. The first pass places initial buckets optimally, focusing on right-side placements. The second pass revisits earlier decisions, adjusting by potentially placing missing left-side buckets if needed, ensuring all hamsters receive feed.
The C solution uses a simple array `visited` to track bucket placement from the first pass, ensuring each bucket is recorded. The second pass checks hamsters not yet marked with a potential bucket and ensures they can still be fed by placing it at `i - 1`. If not possible, it returns -1.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to `visited` array.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the string. |
| Two-Pass Strategy | Time Complexity: O(n), where n is the length of the string. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Placement | O(n) | O(1) | Best general solution. Minimal logic with optimal bucket sharing. |
| Two-Pass Strategy | O(n) | O(n) | Useful when separating forced placements from optimal placements for clarity. |
Video Solution
Leetcode 2086. Minimum Number of Food Buckets to Feed the Hamsters (greedy) • LetsCode • 684 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Minimum Number of Food Buckets to Feed the Hamsters easy or hard?
Minimum Number of Food Buckets to Feed the Hamsters Python/Java solution
How to solve Minimum Number of Food Buckets to Feed the Hamsters in O(n)?
What is the best approach for Minimum Number of Food Buckets to Feed the Hamsters?
Is Minimum Number of Food Buckets to Feed the Hamsters asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Food Buckets to Feed the Hamsters?
What is the time complexity of Minimum Number of Food Buckets to Feed the Hamsters?
Ready to solve this problem?
Practice Minimum Number of Food Buckets to Feed the Hamsters with our built-in code editor and test cases.
Practice on FleetCode