Koko Eating Bananas

35 min · minEatingSpeed()

Eating twice as fast never takes more time. That one-way relationship turns an enormous range of possible speeds into a search problem.

You're given banana pile sizes in piles and a total of h hours. At an integer speed x bananas per hour, a pile of size p takes ceil(p / x) whole hours, where the ceiling rounds a fraction up to the next integer. Return the smallest positive speed that finishes every pile within h hours.

A few ground rules:

Work on only one pile during an hour; spare time from a finished pile isn't carried into another pile.
h is at least the number of piles, so a valid speed always exists.
The answer must be an integer.

Constraints

1 <= piles.length <= 100_000
piles.length <= h <= 1_000_000_000
1 <= piles[i] <= 1_000_000_000

Hints

Write the cost of a speed

For a candidate speed, add ceil(pile / speed) across all piles. The candidate works when that total is at most h.

Find the search bounds

Speed 1 is the slowest candidate worth testing. max(piles) always finishes each pile in one hour, so no faster speed can be minimal.

Use the one-way switch

If a speed works, every faster speed works. If it fails, every slower speed fails. Binary search for the first speed on the working side.

Follow-up

Can your feasibility check stop early once its running hour count already exceeds h?

Visible cases

Examples

Example 1

ready

Input: piles = [ 3, 6, 7, 11 ] h = 8
Expected: 4
Why: speed 4 needs 1 + 2 + 2 + 3 = 8 hours

Example 2

ready

Input: piles = [ 30, 11, 23, 4, 20 ] h = 5
Expected: 30
Why: five hours means every pile must finish in one hour

Example 3

ready

Input: piles = [ 9 ] h = 3
Expected: 3
Why: one pile of 9 takes exactly three hours at speed 3

Interview signal

Asked at

GoogleAmazonDoorDash

Try every speed

Start at speed 1, compute the required hours, and increase the speed until one works.

def min_eating_speed(piles: list[int], h: int) -> int:
    for speed in range(1, max(piles) + 1):
        hours = sum((pile + speed - 1) // speed for pile in piles)
        if hours <= h:
            return speed
    return max(piles)

Time O(n · maxPile). Space O(1). A pile may be as large as one billion, so trying speeds one by one is the real problem.

Binary search the speed

A candidate speed is feasible when it finishes within h hours. Feasibility is monotonic: once a speed works, every larger speed works too. Search the integer range from 1 through max(piles) for the first feasible value.

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum((pile + speed - 1) // speed for pile in piles)
 
    left, right = 1, max(piles)
    while left < right:
        middle = left + (right - left) // 2
        if hours_needed(middle) <= h:
            right = middle
        else:
            left = middle + 1
    return left

When middle works, keep it: it may be the first feasible speed. When it fails, discard it and everything slower. The pointers meet exactly at the boundary between failure and success.

Time O(n log maxPile). Space O(1). Each feasibility check scans the piles, and binary search performs logarithmically many checks.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraypiles: int[] · h: int

Expected

Run: visible + custom · Submit: full suite