Coding Interview PatternsKoko Eating Bananas
MediumModified Binary Search
Koko Eating Bananas
Explanation & Solution
Description
Koko loves to eat bananas. There are n piles of bananas, the i-th pile has piles[i] bananas. The guards will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses a pile and eats k bananas from it. If the pile has less than k bananas, she eats all of them and won't eat any more during that hour.
Return the minimum integer k such that she can eat all the bananas within h hours.
Input:piles = [3, 6, 7, 11], h = 8
0
3
1
6
2
7
3
11
Output: 4
Explanation: At speed 4, Koko eats: [1, 2, 2, 3] = 8 hours total.
Constraints
1 <= piles.length <= 10^4piles.length <= h <= 10^91 <= piles[i] <= 10^9
Approach
Modified Binary Search pattern
1. Define the Search Space
- The minimum possible speed is
1(eat 1 banana per hour). - The maximum needed speed is
max(piles)(eat the largest pile in 1 hour).
2. Binary Search on Speed
- Set
lo = 1,hi = max(piles). - For candidate speed
mid, compute total hours needed:sum of ceil(pile / mid)for each pile.
3. Check Feasibility
- If total hours
<= h, speedmidworks → try slower:hi = mid. - Otherwise, need faster:
lo = mid + 1.
4. Return the Minimum Speed
- When
lo === hi, we've found the minimum valid speed.
🧠 Key Insight
- This is a classic binary search on the answer pattern. Instead of searching a sorted array, we search over the space of possible answers and use a feasibility check to guide the search.
Time
O(n · log(max(piles))) — binary search on speed, linear feasibility check.Space
O(1).Visualization
Input:
[3, 6, 7, 11], h = 8
—
Press ▶ or use ← → to step through
Pointer iPointer jProcessedDone
23 steps