Koko Eating Bananas

Koko must eat all the bananas in a set of piles within h hours, eating at a constant speed of k bananas per hour per pile. Find the minimum integer k that lets her finish in time.

MediumRecommendedBinary Search on AnswerLeetCode

Why solve this?

It's the canonical 'binary search on the answer' problem: there's no array to search — the search space is the set of possible eating speeds.

Pattern recognition

When a problem asks for the minimum/maximum value of some parameter such that a condition holds, and 'can this value satisfy the condition' is monotonic (easier to check as the value grows), binary search directly on that value's range.

Prerequisites

Binary Search
Greedy Algorithms

Hints

Forget searching an array — the thing you're searching over is the eating speed k itself, from 1 to the largest pile.
Write a helper: given a speed k, can Koko finish all piles within h hours?
That helper's answer only ever flips from 'no' to 'yes' as k increases — that monotonicity is what makes binary search valid here.

Approach

Binary search over candidate speeds `k` in `[1, max(piles)]`. For a given `k`, compute the total hours needed as the sum of `ceil(pile / k)` over all piles; this is feasible if the total is `<= h`. Because feasibility is monotonic in `k` (a faster speed never needs more hours), binary search for the smallest feasible `k`: if `k` is feasible, try smaller (`hi = mid`), otherwise go larger (`lo = mid + 1`).

Java solution

Solution.java

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int pile : piles) {
            hi = Math.max(hi, pile);
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (hoursNeeded(piles, mid) <= h) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private long hoursNeeded(int[] piles, int speed) {
        long hours = 0;
        for (int pile : piles) {
            hours += (pile + speed - 1) / speed;
        }
        return hours;
    }
}

Time: O(n log m), m = max pile sizeSpace: O(1)