How to Solve: Koko Eating Bananas (Binary Search on Answer) – Complete Guide

How to Solve: Koko Eating Bananas (Binary Search on Answer) – Complete Guide

? Introduction

"This problem appears in 1 out of every 3 FAANG onsite interviews—mastering it proves you can optimize under constraints and apply binary search beyond sorted arrays, a skill that separates L4 from L5 engineers."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Search – How to search in a sorted array in O(log n) time. 2. Time Complexity Analysis – How to compute the runtime of a loop or function. 3. Edge Case Handling – How to handle minimum/maximum bounds and integer overflows.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you see a "minimum/maximum under constraints" problem:

1. Identify the Search Space
2. What is the minimum possible answer (left)?
3. What is the maximum possible answer (right)?

4. Example: For Koko, left = 1 (slowest speed), right = max(piles) (fastest speed).

5. Define the Condition Function

6. Write a helper function f(k) that returns True if k satisfies the problem’s constraints.

7. Example: f(k) = True if Koko can eat all bananas in ≤ h hours at speed k.

8. Check Monotonicity

9. If f(k) is True, then f(k+1) must also be True (or vice versa).

10. If not, binary search won’t work—rethink the approach.

11. Binary Search Setup

12. Initialize left and right.

13. While left < right:

    • Compute mid = left + (right - left) // 2.
    • If f(mid) is True, search left half (right = mid).
    • Else, search right half (left = mid + 1).

14. Return the Answer

15. After the loop, left will be the smallest valid k.

16. Verify with f(left) (optional, but good for debugging).

17. Edge Cases & Optimization

18. What if h < len(piles)? (Impossible, return -1.)
19. What if h == len(piles)? (Answer is max(piles).)
20. Can you optimize f(k)? (e.g., precompute max(piles).)

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 875. Koko Eating Bananas)

Problem: Koko wants to eat all bananas in piles within h hours. She can eat at most k bananas per hour. Find the minimum k such that she finishes in ≤ h hours.

Solution (Step-by-Step): 1. Search Space:
- left = 1 (slowest speed).
- right = max(piles) (fastest speed, eats one pile in 1 hour).

1. Condition Function (canEat):
   python
def canEat(piles, k, h):
hours = 0
for pile in piles:
hours += (pile + k - 1) // k # Equivalent to math.ceil(pile / k)
return hours <= h

2. Binary Search:
   python
def minEatingSpeed(piles, h):
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if canEat(piles, mid, h):
right = mid
else:
left = mid + 1
return left

3. Time Complexity:

4. O(n log m), where n = len(piles), m = max(piles).

5. canEat is O(n), and binary search runs O(log m) times.

6. Why This Works:

7. The condition canEat(k) is monotonic: If k works, then k+1 also works.
8. Binary search finds the smallest k where canEat(k) is True.

Example 2 – Medium (Follow-up: Minimum Time to Complete Trips)

Problem: You have n buses, each with a time[i] to complete one trip. Find the minimum time to complete at least totalTrips trips.

Solution: 1. Search Space:
- left = 1 (minimum possible time).
- right = min(time) totalTrips (worst case: slowest bus does all trips).

1. Condition Function (canComplete):
   python
def canComplete(time, totalTrips, T):
trips = 0
for t in time:
trips += T // t
return trips >= totalTrips

2. Binary Search:
   python
def minimumTime(time, totalTrips):
left, right = 1, min(time) totalTrips
while left < right:
mid = left + (right - left) // 2
if canComplete(time, totalTrips, mid):
right = mid
else:
left = mid + 1
return left

3. Why This Works:

4. The number of trips is non-decreasing in T.
5. Binary search finds the smallest T where canComplete is True.

Example 3 – Hard (Follow-up: Minimum Number of Days to Make m Bouquets)

Problem: You have bloomDay array where bloomDay[i] is the day flower i blooms. You need m bouquets, each with k adjacent flowers. Find the minimum number of days to make m bouquets.

Solution: 1. Search Space:
- left = 1 (minimum day).
- right = max(bloomDay) (maximum day).

1. Condition Function (canMakeBouquets):
   python
def canMakeBouquets(bloomDay, m, k, day):
bouquets = 0
flowers = 0
for bloom in bloomDay:
if bloom <= day:
flowers += 1
if flowers == k:
bouquets += 1
flowers = 0
else:
flowers = 0
return bouquets >= m

2. Binary Search:
   python
def minDays(bloomDay, m, k):
if m k > len(bloomDay):
return -1
left, right = 1, max(bloomDay)
while left < right:
mid = left + (right - left) // 2
if canMakeBouquets(bloomDay, m, k, mid):
right = mid
else:
left = mid + 1
return left

3. Why This Works:

4. The number of bouquets is non-decreasing in day.
5. Binary search finds the smallest day where canMakeBouquets is True.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s the 30-second version before your interview: 1. Identify the search space: left is the smallest possible answer, right is the largest. 2. Write f(k): A helper that checks if k works. 3. Check monotonicity: If k works, then k+1 must work. 4. Binary search: While left < right, adjust left or right based on f(mid). 5. Return left: It’s the smallest valid k.

This pattern appears in minimum/maximum under constraints problems—like Koko’s bananas, bus trips, or bouquets. If you see ‘minimum time’ or ‘maximum speed,’ think binary search on answer.

Now go crush that interview!"

? Final Notes

• Practice Problems:
• LeetCode 875. Koko Eating Bananas
• LeetCode 1011. Capacity To Ship Packages Within D Days
• LeetCode 1283. Find the Smallest Divisor Given a Threshold
• Time Complexity: O(n log m) (where m is the search space size).
• Space Complexity: O(1) (no extra space).

You’re now ready to solve any "binary search on answer" problem in a FAANG interview! ?