The problem
Koko has piles of bananas and h hours. Each hour she picks one pile and eats up to k bananas from it (if the pile has fewer, she finishes it and waits). Find the smallest eating speed k that lets her finish every pile within h hours.
Input: piles = [3, 6, 7, 11], h = 8 Output: 4
Picture it
Picture the banana piles and a speed dial. For any speed we can quickly count the hours needed: each pile takes ⌈pile ÷ speed⌉ hours. Faster speeds always need fewer or equal hours, so the speeds form a sorted yes/no line: too slow … too slow, fast enough … fast enough. Binary search finds the first “fast enough” speed.
How to recognise it
- You must find the smallest (or largest) value of a setting, here the speed k, that still makes something feasible.
- Feasibility is monotone: if speed k is fast enough, every faster speed is too. So the speeds split into "too slow" followed by "fast enough", with one boundary.
- Checking a single speed is easy (add up the hours), but there are far too many speeds to try one by one.
- "Minimise the largest", "smallest capacity", "least speed" plus a cheap check are the classic signs of binary search on the answer.
Start with brute force
Try k = 1, 2, 3, ... and return the first speed whose total hours fit within h. (p + k - 1) // k is the ceiling of p / k in whole numbers.
def min_speed_brute(piles, h):
k = 1
while sum((p + k - 1) // k for p in piles) > h:
k += 1
return k
Each check is O(n), and the answer can be as large as max(piles), so time is O(n · max(piles)) and space is O(1). With 10^4 piles of 10^9 bananas and h = 10^4, the answer is 10^9, so this makes about 10^9 checks of 10^4 piles each: around 10^13 steps.
From brute force to the idea
- Find the waste. The brute force tests speeds in order, but once one speed is known to work, every faster one works too. A single test tells you about a whole range of speeds.
- Search the speeds, not the piles. Set
lo = 1andhi = max(piles). The answer is somewhere inlo..hi, andhialways works because h is at least the number of piles. - Test the middle speed. For
k = (lo + hi) // 2, compute the hours:sum(ceil(p / k) for p in piles). Each pile takes whole hours, so round up. - Keep the half that holds the boundary. If
hours <= h, k works and may be the answer, so keep it:hi = k. Otherwise k is too slow, and so is everything below it:lo = k + 1. - Stop when one speed is left. The loop runs
while lo < hi, and when it endslo == hiis the smallest speed that works.
This is the key idea: binary search over the possible answers, using "does this speed finish in time?" as the yes/no test.
The key idea
Binary search on the answer: if a speed works, every faster speed works too. O(n · log(max pile)).
Python solution
def min_eating_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
k = (lo + hi) // 2
hours = sum(ceil(p / k) for p in piles)
if hours <= h:
hi = k # fast enough; try slower
else:
lo = k + 1 # too slow
return loLeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import ceil
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · max(piles)): up to max(piles) speeds, each checked in O(n) | O(1) |
| Binary search on k (shown code) | O(n · log(max(piles))): about 30 checks for 10^9, each O(n) | O(1): the generator in sum stores nothing |
Edge cases
- Imports: the shown code calls
ceilwithout importing it. It needsfrom math import ceil, or the first check raisesNameError. - The example (
[3, 6, 7, 11], h = 8): returns 4. - h equals the number of piles (
[30, 11, 23, 4, 20], h = 5): every pile needs its own hour, so the answer ismax(piles)= 30. - Lots of time (
[5], h = 10^9): returns 1, the smallest speed allowed. - One huge pile (
[10**9], h = 2): returns 500,000,000. - Float rounding:
ceil(p / k)divides in floating point. For piles below 2^53 it is exact enough to round up correctly;(p + k - 1) // kavoids floats entirely.
Common mistakes
- Rounding down with
p // k. A pile of 7 at speed 4 takes 2 hours, not 1. - Writing
hi = k - 1when k works. That can throw away the answer itself. - Starting
hiatmax(piles) - 1, or at the average pile size. The search can then never reach the true answer when it is the largest pile. - Starting
loat 0, which can lead to a division by zero.
Packages with weights weights must be shipped in order, one ship per day. Each day you load packages from the front until the next one would exceed the ship's capacity. Find the smallest capacity that ships everything within days days. For weights 1 to 10 and 5 days the answer is 15. Describe your approach, then write it if you like.
Compare with our answer
It is the same shape: a larger capacity never needs more days. The capacity must be at least the heaviest package and at most the total weight. Binary search between them, checking each capacity by simulating the days greedily.
def ship_within_days(weights, days):
def days_needed(cap):
d, load = 1, 0
for w in weights:
if load + w > cap: # start a new day
d, load = d + 1, 0
load += w
return d
lo, hi = max(weights), sum(weights)
while lo < hi:
cap = (lo + hi) // 2
if days_needed(cap) <= days:
hi = cap
else:
lo = cap + 1
return lo
Time O(n · log(sum(weights))), space O(1).
A strong answer mentions: why feasibility is monotone in the capacity, why lo starts at the heaviest package (smaller ships cannot carry it), and that the greedy day count is O(n).
1. A printer farm must finish n jobs, splitting them in order between k printers. You must find the smallest possible time for the busiest printer. Which approach fits best?
"Smallest limit that is feasible" with a monotone check is binary search on the answer, as in Koko. Sorting breaks the required order, trying every split is exponential, and equal job counts ignore job lengths.
2. Why does the shown code need about 30 checks for piles of up to 10^9?
The binary search runs over speeds, not piles, so the number of steps is about log2(10^9) ≈ 30. Each step still costs O(n) to add up the hours.
3. A learner starts with hi = max(piles) - 1. For piles [3, 6, 7, 11], which h now gives a wrong answer?
With four piles and four hours, each pile needs its own hour, so the answer is 11, which is outside the new range; the function returns 10. For larger h the answer is below 11, so the smaller range still contains it.
Score 60% or more and the lesson is marked complete.