Watch 2 video solutions for Minimum Number of Food Buckets to Feed the Hamsters, a medium level problem involving String, Dynamic Programming, Greedy. This walkthrough by LetsCode has 647 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105hamsters[i] is either'H' or '.'.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 | 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. |