~/problems / Binary search / Binary search on the answer

Koko Eating Bananas

medium ~25 min

Write min_eating_speed(piles: list[int], h: int) -> int.

There are several piles of snacks, piles[i] snacks in pile i. You pick an integer speed k >= 1. Every hour you choose one pile and eat up to k snacks from it; if the pile has fewer than k left you finish it and wait out the rest of the hour (you never start a second pile in the same hour). So pile p takes ceil(p / k) hours. Return the smallest k that lets you finish all piles within h hours.

Example: piles = [4, 9, 6], h = 5 gives 5 (hours 1 + 2 + 2 = 5; speed 4 would need 1 + 3 + 2 = 6). With h = 3 the answer is 9.

Constraints: 1 <= len(piles) <= h <= 10^9, len(piles) <= 10^4, 1 <= piles[i] <= 10^9.

Trying speeds 1, 2, 3, ... is far too slow; aim for O(n log(max(piles))).

Show hint

the hours needed only go down as k goes up. Checking a single candidate k takes one pass over the piles, so find the boundary with as few checks as possible.

Topic: Binary search on the answer. Monotonic feasibility check + search the smallest value that works.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc