Pattern this teaches:Binary Search on Answer
Koko Eating Bananas
A medium Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 1
- Core for
- 7 roles
The problem
A monkey has h hours to finish several piles of bananas. She picks one eating speed k and, each hour, eats up to k bananas from a single pile; a pile with fewer than k left is finished that hour and the rest of the hour is wasted. Find the slowest whole-number speed that still clears every pile within h hours.
Example 1
- Input
- piles = [4,5,9,13], h = 7
- Output
- 5
- Why
- At speed 5 the piles take 1+1+2+3 = 7 hours, exactly the limit; speed 4 needs 10.
Example 2
- Input
- piles = [25,9,18,3,15], h = 5
- Output
- 25
- Why
- Five piles in five hours means one pile per hour, so Koko must match the biggest pile.
Constraints
- 1 <= piles.length <= 10^5
- piles.length <= h <= 10^9
- 1 <= piles[i] <= 10^9
How to think about it
Updated 2026-09-29Total eating time is a monotonically decreasing function of speed: faster speeds never increase the hours required. Because the outcome transitions cleanly from impossible to possible at a single speed threshold, you can binary search directly on the speed value.
Approaches, worst first
Sequential speed increment
time O(max(piles) * n) · space O(1)
Start speed k at 1 and compute total hours until the sum drops below or equals h. Correct due to monotonicity, but scanning speeds one by one is far too slow when piles contain up to 10^9 bananas.
Binary search on eating rateWrite this one
time O(n log(max(piles))) · space O(1)
Binary search over speeds between 1 and the maximum pile size. For each midpoint speed, accumulate ceiling division hours across all piles to check feasibility within h hours.
Where people lose marks · 3
- Ceil division computed with standard floating-point arithmetic introduces rounding precision loss on numbers near 10^9; use integer arithmetic (pile + speed - 1) / speed.
- Summing hours across piles into a 32-bit signed integer can exceed 2^31 - 1 when speeds are very small; use 64-bit integer accumulators.
- Setting the search upper bound to a fixed small constant instead of max(piles) fails when h equals the number of piles.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .