Introduction

Some greedy problems look simple at first, but the order in which decisions are made can make a big difference.

In this problem, each 'H' represents a hamster and each '.' represents an empty position where a food bucket can be placed. Every hamster needs at least one bucket immediately to its left or right.

The goal is to feed every hamster using the minimum number of buckets.

The key observation is:

When a hamster needs a bucket, placing it on the right side is generally the best choice because that bucket may also help a future hamster.

This creates a natural left-to-right greedy strategy.

Question Link

LeetCode 2086 – Minimum Number of Food Buckets to Feed the Hamsters

Understanding the Problem

Consider:

The hamster on the left and the hamster on the right can both use the same bucket:

So only one bucket is required.

But consider:

One bucket cannot feed both hamsters because they are two positions apart:

The second hamster still has no adjacent bucket.

Therefore, two buckets are necessary:

There is also an impossible case:

The middle hamster has no empty position next to it, so there is no way to feed it.

Greedy Approach

The string is scanned from left to right.

Whenever a hamster 'H' is encountered:

1. If it already has a bucket on either side, nothing needs to be done.
2. Otherwise, if the right position is empty, place a bucket there.
3. If the right position cannot be used, try the left position.
4. If both neighboring positions contain hamsters, feeding that hamster is impossible, so return -1.

A character '0' is used to represent a bucket that has already been placed.

Why prefer the right side?

Suppose the current hamster is:

Placing the bucket on the right side of the current hamster gives:

The next hamster is also fed by the same bucket.

Therefore, choosing the right side can allow one bucket to serve two consecutive hamsters.

Java Solution

The following implementation directly simulates the placement of buckets inside a character array.

Dry Run

Consider:

Initial array:

First hamster

The hamster at index 1 has:

The algorithm prefers the right side.

Place a bucket at index 2:

Bucket count:

Second hamster

The hamster at index 3 checks its neighbors:

A bucket already exists at index 2, so this hamster is already fed.

No new bucket is required.

Final arrangement:

Answer:

Another Example

Consider:

Initially:

The first hamster places a bucket on its right:

The second hamster does not have a bucket next to it, so it places one on its left:

Total:

Impossible Case

Consider:

The middle hamster has hamsters on both sides:

There is no empty adjacent position for it.

Even if buckets are placed at both ends:

the middle hamster still cannot reach a bucket.

Therefore:

Complexity Analysis

Let n be the length of the string.

Time Complexity

The array is traversed once:

O(n)

Each position is processed a constant number of times.

Space Complexity

The string is converted into a character array:

O(n)

Apart from that, only a constant amount of extra variables is used.

Why This Greedy Strategy Works

The important decision is what to do when a hamster has no bucket nearby.

If the right position is empty, placing the bucket there is preferred because:

becomes:

One bucket now handles two hamsters.

If the bucket were instead placed on the left, the next hamster might still require another bucket.

Therefore, processing from left to right and preferring the right side makes each bucket as useful as possible.

The already placed buckets are marked as '0', allowing later hamsters to immediately recognize that they are already fed.

A Useful Pattern to Remember

This problem is a good example of local greedy decisions producing a globally optimal result.

When a position needs a resource and there are multiple valid choices, ask:

Which choice can also help future elements?

Here, the answer is usually the right-side bucket.

This same type of reasoning appears frequently in greedy problems involving:

1. Intervals
2. Arrays
3. String simulations
4. Scheduling
5. Resource placement
6. Covering neighboring elements

Interview Tip

For an interview, the most important part is not memorizing the implementation.

The core reasoning should be clear:

Hamster already fed → skip

Right side empty → place bucket there

Otherwise left side empty → place bucket there

Both sides are hamsters → impossible

The right-side preference is the key optimization because a bucket can potentially serve the next hamster as well.

Conclusion

LeetCode 2086 is a compact greedy problem where careful local decisions are enough to obtain the minimum number of buckets.

The main idea is to scan from left to right, avoid placing unnecessary buckets, and whenever a bucket is required, prefer the right side whenever possible. Existing buckets are marked directly in the array so that later hamsters can reuse them.

The resulting solution runs in O(n) time, making it easily suitable for the constraint of up to 10⁵ positions.