LeetCode 875: Koko Eating Bananas

Problem Restatement

Koko has several piles of bananas.

The array piles tells us how many bananas are in each pile.

Koko chooses an eating speed:

k

This means she can eat up to k bananas from one pile in one hour.

Rules:

1. Each hour, she chooses one pile.
2. If the pile has at least k bananas, she eats exactly k.
3. If the pile has fewer than k bananas, she eats the whole pile.
4. She does not eat from another pile during that same hour.

Given h hours, return the minimum integer speed k such that Koko can eat all bananas within h hours.

Input and Output

Function shape:

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        ...

Examples

Example 1:

piles = [3, 6, 7, 11]
h = 8

If k = 4, the hours needed are:

Total:

1 + 2 + 2 + 3 = 8

So speed 4 works.

If k = 3, the hours are:

1 + 2 + 3 + 4 = 10

That is too slow.

So the answer is:

4

Example 2:

piles = [30, 11, 23, 4, 20]
h = 5

There are five piles and five hours.

Koko must finish each pile in one hour.

So she needs speed equal to the largest pile:

30

Example 3:

piles = [30, 11, 23, 4, 20]
h = 6

The minimum speed that works is:

23

First Thought: Try Every Speed

A direct solution is to try every possible speed from 1 to max(piles).

For each speed, compute how many hours Koko needs.

Return the first speed that finishes within h hours.

This is correct, but it can be too slow because piles[i] can be very large.

Key Insight

The answer has a monotonic property.

If Koko can finish at speed k, then she can also finish at any speed larger than k.

If she cannot finish at speed k, then any smaller speed also fails.

So the speeds look like this:

fail, fail, fail, pass, pass, pass

We need the first passing speed.

That is a binary search problem.

For a pile with bananas bananas, the hours needed at speed k is:

ceil(bananas / k)

In integer arithmetic:

(bananas + k - 1) // k

Algorithm

Search over possible speeds.

The smallest possible speed is:

1

The largest useful speed is:

max(piles)

For each middle speed:

1. Compute the total hours needed.
2. If total hours is less than or equal to h, this speed works.
3. Try a smaller speed by moving right.
4. Otherwise, the speed is too slow.
5. Try a larger speed by moving left.

When the search ends, left is the minimum valid speed.

Correctness

For any fixed speed k, the function hours(k) computes the exact number of hours needed because each pile requires ceil(pile / k) hours.

If hours(k) <= h, then speed k is valid. Any larger speed can only reduce or keep the same number of hours, so all larger speeds are also valid.

If hours(k) > h, then speed k is invalid. Any smaller speed can only increase or keep the same number of hours, so all smaller speeds are also invalid.

Therefore, the valid speeds form a suffix of the search range.

Binary search preserves the smallest valid speed inside the search range. When the middle speed works, the algorithm keeps it as a possible answer by moving right = mid. When it fails, the algorithm removes it and all smaller speeds by moving left = mid + 1.

When left == right, only one speed remains. Since the smallest valid speed was never removed, that speed is the answer.

Complexity

Let:

n = len(piles)
m = max(piles)

Implementation

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        left = 1
        right = max(piles)

        while left < right:
            mid = (left + right) // 2

            hours = 0
            for pile in piles:
                hours += (pile + mid - 1) // mid

            if hours <= h:
                right = mid
            else:
                left = mid + 1

        return left

Code Explanation

The search range is:

left = 1
right = max(piles)

Speed 1 is the slowest possible speed.

Speed max(piles) can finish every pile in at most one hour.

The loop continues while more than one candidate speed remains:

while left < right:

We test the middle speed:

mid = (left + right) // 2

Then compute the total hours:

hours = 0
for pile in piles:
    hours += (pile + mid - 1) // mid

The expression:

(pile + mid - 1) // mid

is integer ceiling division.

If the speed works:

if hours <= h:
    right = mid

we try to find a smaller valid speed.

Otherwise:

else:
    left = mid + 1

the speed is too slow, so we search higher speeds.

Finally:

return left

returns the smallest speed that works.

Testing

def test_min_eating_speed():
    s = Solution()

    assert s.minEatingSpeed([3, 6, 7, 11], 8) == 4

    assert s.minEatingSpeed([30, 11, 23, 4, 20], 5) == 30

    assert s.minEatingSpeed([30, 11, 23, 4, 20], 6) == 23

    assert s.minEatingSpeed([1], 1) == 1

    assert s.minEatingSpeed([312884470], 312884469) == 2

    print("all tests passed")

test_min_eating_speed()

Test meaning: