875. Koko Eating Bananas - Detailed Explanation
Problem statement
Koko loves eating bananas. There are n piles of bananas, where the i-th pile has piles[i] bananas. The guards have gone for h hours, and Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats up to k bananas from that pile. If she finishes a pile, she moves to the next one.
Koko wants to eat all the bananas within h hours. Find the minimum integer k such that she can finish all the bananas in time.
Examples
Example 1
Input:
piles = [3, 6, 7, 11] h = 8
Output:
4
Explanation: If Koko eats at a rate of 4 bananas per hour, she will finish all the piles in exactly 8 hours.
Example 2
Input:
piles = [30, 11, 23, 4, 20] h = 5
Output:
30
Explanation: She must eat at a rate of 30 bananas per hour to finish all the bananas in 5 hours.
Example 3
Input:
piles = [30, 11, 23, 4, 20] h = 6
Output:
23
Explanation: With 6 hours available, Koko can eat at a rate of 23 bananas per hour and finish all piles in time.
Constraints
1 <= piles.length <= 10^41 <= piles[i] <= 10^9piles.length <= h <= 10^9
Hints to solve the problem
- Brute force approach: Try all possible eating speeds from 1 up to the size of the largest pile. Check if Koko can finish within
hhours at that speed. - Optimized approach: Use binary search to find the minimum valid
kinstead of testing every speed in order. - Key observation: A slower eating speed takes longer, and a faster speed finishes sooner. Feasibility therefore flips exactly once as
kgrows, and that single flip is what binary search locates.
The third hint names the pattern. This question belongs to Modified Binary Search, which means you binary search a range of candidate answers rather than a sorted array. The range here is the eating speed, 1 through max(piles), and the test for each candidate is "can Koko finish in h hours at this speed". It is one of the highest-yield entries among the recurring coding interview patterns, because the same move solves shipping capacity, divisor thresholds, and several scheduling questions.
Approach 1: brute force (try all speeds)
Explanation
- Iterate over possible speeds
kfrom 1 tomax(piles)(the size of the largest pile). - For each speed
k, calculate the total time required by summing upceil(pile / k)for each pile. - If the total hours needed is
<= h, then Koko can finish with speedk. Return thiskas soon as you find the first that works, which is the minimum possible. - If none of the speeds up to
max(piles)work, which the constraints rule out, return -1.
Python code
Complexity analysis
- Time complexity: O(N * M), where N is the number of piles and M is the size of the largest pile. In the worst case that reaches
10^9 * 10^4operations, far beyond any time limit. The brute force will time out on large inputs. - Space complexity: O(1), since we only use a few extra variables for counting time.
Approach 2: optimized binary search
Explanation
- We can use binary search on the range of possible eating speeds, from 1 to
max(piles). - Set
low = 1andhigh = max(piles). Whilelow < high:- Choose
mid = (low + high) // 2as a candidate speed. - Compute the total hours required at speed
midby summingceil(pile / mid)for each pile. - If the total hours are
<= h, thenmidis fast enough, possibly faster than needed. Try a smaller speed by settinghigh = mid. - If the total hours are
> h, thenmidis too slow, so the speed has to go up. Setlow = mid + 1.
- Choose
- When the loop ends,
lowequalshigh, and that value is the smallest speed that finishes withinhhours.
Notice what the search never does: it never evaluates most candidate speeds at all. Each test tells you which half of the range still holds the answer, so about log M tests settle it. If that boundary-hunting feels unfamiliar, Find Peak Element drills the same discard-half reasoning on a simpler input, and the mock interview course teaches this question directly in its Koko Eating Bananas lesson.
Python code
Java code (binary search approach)
Note: In the Java code above, (pile + mid - 1) / mid computes the ceiling of pile/mid with integer arithmetic.
Complexity analysis
- Time complexity: O(N * log M), where N is the number of piles and M is the maximum pile size. The binary search runs in about
log Msteps, and each step computes the total hours in O(N). That stays fast even at the top of the constraint range. - Space complexity: O(1), since the extra space used is minimal.
Edge cases
- Single pile: With
piles = [10]andh = 5, a speed of 2 is enough, becauseceil(10 / 2)is 5 hours. A speed of 1 would need 10 hours, so the answer is 2. Onlyh = 1would force a speed of 10. - Plenty of time: If
his very large, say much larger than the total number of bananas, Koko can eat as slowly as 1 banana per hour and still finish. The answer is then 1. - Huge pile sizes: Very large pile values cost the binary search only a few more steps, while a linear scan over speeds becomes hopeless.
Common mistakes
- Using floor division instead of ceiling when calculating hours, for example
sum(pile // k)in Python. That underestimates the hours, because leftover bananas in a pile still occupy a full extra hour. - Testing every possible speed on large inputs. The feasible region is monotonic: once a speed works, every faster speed works too. That property is the license to binary search, so use it.
- Setting
highto the sum of all piles rather thanmax(piles). The search still returns the right answer, but no speed above the largest pile ever helps, since one hour per pile is already the floor on time.
Alternative variations
- Minimize maximum workload: Instead of time, distribute the piles among several workers and minimize the largest amount any one worker must eat. This is the same load-balancing shape, answered with binary search or a greedy rule.
- Split Array Largest Sum: Split an array into a given number of subarrays and minimize the largest subarray sum. This also binary searches for an optimal threshold.
Related problems for practice
- Split Array Largest Sum. Partition an array into subarrays so that the largest subarray sum is minimized, with binary search or dynamic programming.
- Capacity To Ship Packages Within D Days. Find the minimum ship capacity that clears the packages before a deadline, by binary searching the capacity.
- Find Smallest Divisor Given a Threshold. Determine the smallest divisor for which the sum of the quotients stays within a given threshold, by binary searching the divisor.
All three reuse the structure you just applied: define the candidate range, write one feasibility test, then discard half the range per step. Several of them appear on the Blind 75 list, and Grokking the Coding Interview collects them into a single chapter so the pattern, not the individual question, is what you practice.
GET YOUR FREE
Coding Questions Catalog
$99
$197
$72
