Koko Eating Bananas

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Examples

Example 1

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation: At speed k=4, Koko eats: ceil(3/4)=1h, ceil(6/4)=2h, ceil(7/4)=2h, ceil(11/4)=3h = 8h total

Example 2

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation: With only 5 hours and 5 piles, Koko must eat 1 pile per hour. Max pile is 30, so k=30.

Example 3

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Explanation: At k=23, she finishes in exactly 6 hours.

Intuition

This is a binary search on the answer problem! The key insight:

• Minimum possible k: 1 banana/hour (too slow)
• Maximum possible k: max(piles) (eat largest pile in 1 hour)
• Search space: All speeds from 1 to max(piles)
• Monotonic property: If k works, any k' > k also works

Instead of testing every speed linearly O(max), use binary search O(log max).

Pattern Recognition

This is Binary Search on Answer Space with these characteristics:

• Not searching for element in array
• Searching for optimal value in a range
• Can check if a candidate answer is valid
• Answer space has monotonic property
• Optimization problem (minimize k)

Approach

1. Define Search Space:

   • left = 1 (minimum eating speed)
   • right = max(piles) (maximum eating speed)

2. Binary Search on Speed:

   • Calculate mid = left + (right - left) / 2
   • Check if Koko can finish at speed mid in h hours

3. Check Feasibility:

   • For each pile: hours += ceil(pile / k)
   • If total hours ≤ h: k is feasible, try smaller k
   • Else: k too slow, need larger k

4. Minimize k:

   • If mid works: right = mid - 1 (try slower speed)
   • If mid doesn't work: left = mid + 1 (need faster speed)

5. Return: left (minimum feasible speed)

Edge Cases

• Single pile
• h equals number of piles (must eat 1 pile per hour)
• Very large piles
• h much larger than needed (k=1 works)

Complexity Analysis

• Time Complexity: O(n * log(max)) where n = number of piles, max = largest pile

  • Binary search: O(log(max)) iterations
  • Each iteration checks all piles: O(n)

• Space Complexity: O(1)

  • Only using a few variables