Koko Eating Bananas
Task example: Koko Eating Bananas
Choose the smallest positive integer speed k that lets Koko finish all piles within h hours. During each hour she eats up to k bananas from just one pile; unused time cannot be spent on another pile. The input guarantees h >= len(piles), so a solution exists. Keep piles unchanged.
At k = 4, the piles take 1 + 2 + 2 + 3 = 8 hours. At k = 3, they take 10 hours. Therefore 4 is the minimum speed. Round each pile up separately, not the total banana count.
Try every speed: video explanation
piles = [3, 6, 7, 11], h = 8 → 4
Prefer reading? Follow the steps below.
- Try k = 1, 2, ... up to max(piles). For each speed, reset hours to zero and visit every pile.
- Add (pile + k - 1) // k for each pile. This is integer ceiling division: 7 bananas at speed 3 need 3 hours, not 2.
- Return the first k with hours <= h. Speeds 1, 2, 3, 4 need 27, 15, 10, 8 hours for this example. The first working speed is 4.
Time complexity · O(n · M)
Let n = len(piles) and M = max(piles). Up to M speed checks each visit n piles: O(n · M) worst-case time.
Space complexity · O(1)
Only the speed and counters are stored. The input is not copied: O(1) extra space.
Binary search: video explanation
piles = [3, 6, 7, 11], h = 8 → 4
Prefer reading? Follow the steps below.
- Set left = 1 and right = max(piles). This searches speeds, not indices. The largest pile is a valid speed because every pile then takes one hour.
- While left < right, try k = (left + right) // 2. Add (pile + k - 1) // k over all piles to check this speed.
- If hours <= h, set right = k: this speed works, but a slower one may work too. Otherwise set left = k + 1: this speed and all slower speeds fail.
- When left == right, return left. For the example, tested speeds are 6, 3, 5, 4. Keep k on success; using right = k - 1 could discard the answer.
Feasibility is monotonic: once a speed works, every faster speed works too. Binary search skips whole ranges of speeds instead of testing them individually. No sorting is needed.
Time complexity · O(n · log(M + 1))
Each check costs O(n); the speed range halves each time. Commonly O(n · log M); including the initial maximum scan and M = 1, the precise bound is O(n · log(M + 1)).
Space complexity · O(1)
Only the speed and counters are stored. The input is not copied: O(1) extra space.