LeetCode 875 · Medium · Binary Search

Koko Eating Bananas

Koko has piles of bananas and h hours. Each hour she picks one pile and eats up to k bananas from it. Find the smallest whole speed k that lets her finish every pile within h hours.

O(n log m)time · m = max pile
O(1)space
search kover the answer space

piles: 1–8 integers, 1 to 30 · h: at least the number of piles, at most 99

piles hours each pile takes at speed k: ⌈p / k⌉

Speeds k = 1 … max(piles) the answer space; [l, r] is still in play

public int minEatingSpeed(int[] piles, int h) { int l = 1; int r = Arrays.stream(piles).max().getAsInt(); int res = r; // max(piles) always works while (l <= r) { int k = l + (r - l) / 2; long hours = 0; for (int p : piles) { hours += (p + k - 1) / k; } if (hours <= h) { res = k; // k works; try slower r = k - 1; } else { l = k + 1; // too slow; go faster } } return res;}
l
—
r
—
k
—
hours
—
res
—

Why it works

  1. Brute force tries every speed from 1 up and stops at the first that fits in h hours. Each try costs O(n), and there can be max(piles) tries: O(n·m).
  2. The answer space is sorted by feasibility. If speed k finishes in time, any faster speed does too. So the speeds read "too slow, too slow, …, fits, fits": binary search for the first "fits". Invariant: the answer is res or lies inside [l, r].
  3. O(n log m) time. Each probe halves the speed range, about log₂(m) probes, and each probe sums n pile hours. O(1) extra space.
  4. Pitfall: integer division. A pile of 7 at speed 4 takes 2 hours, not 1, but 7 / 4 is 1 in Java, and Math.ceil(7 / 4) still is, because the division truncates first. Use (p + k - 1) / k, or Math.ceil((double) p / k). Keep hours a long: with 104 piles of 109 the total overflows int. Starting l at 0 would divide by zero (ArithmeticException).
  5. Same pattern: Capacity to Ship Packages Within D Days (1011) and Split Array Largest Sum (410). Binary search the answer whenever a yes/no check is monotonic in it.