Koko Eating Bananas

Problem statement

Koko has n piles of bananas. Pile i has piles[i] bananas. The guards come back in h hours. Each hour she picks one pile and eats k bananas from it. If the pile is smaller than k, she still spends that whole hour and does not start another pile.

Find the smallest integer k such that she can finish every pile before the guards return.

Example:

Input:

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

Expected output:

4

Why: at speed 4 the hours are ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8. Speed 3 needs 10 hours, so 4 is the minimum.

Practice on LeetCode: Koko Eating Bananas

What we are searching for

k is not an index in piles. It is an eating speed. The hours needed at speed k is the sum of ceil(pile / k) over every pile.

That sum only goes down (or stays) as k goes up. If speed k finishes in time, every faster speed does too. If k is too slow, every slower speed is also too slow.

So the feasible speeds look like:

k:        1  2  3  4  5  …  max(piles)
feasible: N  N  N  Y  Y  …  Y

We want the leftmost Y.

Why not try every speed

The slowest she can eat is 1 banana per hour. The fastest useful speed is max(piles) — one pile per hour, and she cannot go faster than that in a way that saves hours (a pile still costs at least one hour).

Trying every k from 1 to max(piles) is O(n · max(piles)). Pile sizes go up to 10^9. That will not run.

Binary search over the speed range is O(n log M), where M is the largest pile.

This is the same “search the answer” pattern as Find the Smallest Divisor Given a Threshold.

Golang Solution

Search k in [1, max(piles)]. For a candidate mid, ask: do the piles finish in at most h hours? If yes, try slower. If no, go faster. The loop is the lower-bound form: high = mid when mid works, low = mid + 1 when it does not. low lands on the smallest feasible speed.

Time: O(n log M) — M is max(piles)
Space: O(1)

import "math"

func minEatingSpeed(piles []int, h int) int {
    maxVal := math.MinInt

    for i := 0; i < len(piles); i++ {
        if maxVal < piles[i] {
            maxVal = piles[i]
        }
    }

    low, high := 1, maxVal
    for low < high {
        mid := low + (high-low)/2
        if feasible(mid, piles, h) {
            high = mid
        } else {
            low = mid + 1
        }
    }
    return low
}

func feasible(mid int, piles []int, h int) bool {
    var temp float64
    for i := 0; i < len(piles); i++ {
        temp += math.Ceil(float64(piles[i]) / float64(mid))
    }
    return int(temp) <= h
}

ceil(a / k) is the hours for one pile: she cannot leave a pile mid-hour and start another. h is always at least n (one hour per pile), so a feasible k exists — max(piles) always works.

Integer-only hours, if you want to drop float64: (piles[i] + mid - 1) / mid.