Koko Eating Bananas

LeetCode 875: Koko Eating Bananas Solution & Explanation

Problem Overview

TL;DR: We use binary search on the range of possible eating speeds to find the minimum integer speed k that allows Koko to finish all bananas within h hours.

In LeetCode 875, we are provided with an array of banana piles and a strict time limit h in hours. We must determine the minimum eating speed k (bananas per hour). The rules dictate that Koko can only eat from one pile per hour. If the pile size is less than k, she finishes the pile and waits for the next hour; she cannot move to another pile within the same hour. This creates a ceiling constraint on time consumption per pile.

The goal of the Koko Eating Bananas problem is to find the smallest integer k such that the sum of hours required for all piles is less than or equal to h.

Brute Force Approach for Koko Eating Bananas

The brute force approach involves checking every possible eating speed starting from the minimum possible speed.

1. Start with k = 1.
2. Calculate the total hours required to eat all bananas at speed k.
3. If the total hours $\le h$, return k.
4. Otherwise, increment k to 2, 3, etc., and repeat.

The maximum possible speed needed is the size of the largest pile (let's call this max(piles)), because eating faster than the pile size does not reduce the time spent on that specific pile (it always takes 1 hour minimum).

Pseudo-code:

max_speed = max(piles)
for k from 1 to max_speed:
    hours_needed = 0
    for pile in piles:
        hours_needed += ceiling(pile / k)
    if hours_needed <= h:
        return k

Time Complexity Analysis: The time complexity is $O(N \cdot M)$, where $N$ is the number of piles and $M$ is the maximum number of bananas in a pile ($10^9$). Given that $M$ can be up to $10^9$, performing a linear scan is computationally infeasible and results in a Time Limit Exceeded (TLE) error. We need a logarithmic approach to search the solution space.

Algorithm Strategy: Binary Search Patterns

We utilize the standard "minimize k" binary search template.

1. Define Boundaries:

   • left: 1 (minimum possible speed).
   • right: Maximum value in piles (sufficient upper bound).

2. Condition Function (canFinish):

   • For a given mid (candidate speed), iterate through piles.
   • Calculate hours for each pile using integer math equivalent to ceiling: (pile + mid - 1) / mid.
   • Sum these hours.
   • Return true if the sum is $\le h$.

3. Binary Search Logic:

   • While left <= right:
     • Calculate mid.
     • If canFinish(mid) is true:
       • Record mid as a potential answer.
       • Try to find a smaller valid speed by moving right to mid - 1.
     • If canFinish(mid) is false:
       • The speed is too slow. Move left to mid + 1.

4. Result:

   • The left pointer (or the variable storing the valid mid) will correspond to the minimum speed.

Execution Flow

Let's trace Example 1: piles = [3, 6, 7, 11], h = 8.

1. Initialization:

   • left = 1
   • right = 11 (max of piles)

2. Iteration 1:

   • mid = (1 + 11) / 2 = 6.
   • Check(6):
     • Pile 3: $\lceil 3/6 \rceil = 1$ hr
     • Pile 6: $\lceil 6/6 \rceil = 1$ hr
     • Pile 7: $\lceil 7/6 \rceil = 2$ hrs
     • Pile 11: $\lceil 11/6 \rceil = 2$ hrs
     • Total: $1+1+2+2 = 6$ hours.
   • $6 \le 8$ is True.
   • Store ans = 6. We might find a smaller speed.
   • right becomes 5.

3. Iteration 2:

   • left = 1, right = 5.
   • mid = (1 + 5) / 2 = 3.
   • Check(3):
     • Pile 3: 1 hr
     • Pile 6: 2 hrs
     • Pile 7: 3 hrs
     • Pile 11: 4 hrs
     • Total: 10 hours.
   • $10 \le 8$ is False.
   • Speed 3 is too slow.
   • left becomes 4.

4. Iteration 3:

   • left = 4, right = 5.
   • mid = (4 + 5) / 2 = 4.
   • Check(4):
     • Pile 3: 1 hr
     • Pile 6: 2 hrs
     • Pile 7: 2 hrs
     • Pile 11: 3 hrs
     • Total: 8 hours.
   • $8 \le 8$ is True.
   • Store ans = 4.
   • right becomes 3.

5. Termination:

   • left = 4, right = 3.
   • Loop terminates. Return 4.

Proof of Correctness

The correctness relies on the Monotonicity Property. The function $f(k) = \text{total hours needed}$ is strictly non-increasing with respect to $k$. Because the function is monotonic, the boolean condition total_hours <= h splits the number line into two contiguous segments: [False, ..., False, True, ..., True]. Binary search is guaranteed to find the boundary between False and True in logarithmic time. Since we always store the valid mid and attempt to move left, the algorithm converges on the minimum k that satisfies the condition.

Pattern Reuse Notes

The "Binary Search on Answer" pattern used in LeetCode 875 is a fundamental technique for optimization problems where the answer lies within a range and satisfies a monotonic condition.

This same logic applies directly to:

• LeetCode 410: Split Array Largest Sum: Binary search the maximum subarray sum. The condition function checks if the array can be split into m subarrays with that sum limit.
• LeetCode 774: Minimize Max Distance to Gas Station: Binary search the distance. The condition checks if we can add k stations to satisfy that distance.
• LeetCode 1011: Capacity To Ship Packages Within D Days: Identical structure. Search for capacity k such that packages are shipped in D days.
• LeetCode 1482: Minimum Number of Days to Make m Bouquets: Binary search the days. The condition checks if m bouquets can be formed given the blooming status.

In all these cases, we replace the linear search of the answer space with binary search, reducing complexity from linear to logarithmic relative to the answer range.

Reference Implementation

C++ Solution for LeetCode 875

1class Solution {
2public:
3    int minEatingSpeed(vector<int>& piles, int h) {
4        int left = 1;
5        int right = 0;
6        
7        // Determine the upper bound of the search space
8        for (int pile : piles) {
9            right = max(right, pile);
10        }
11        
12        int result = right;
13        
14        while (left <= right) {
15            int mid = left + (right - left) / 2;
16            
17            // Calculate hours needed for speed 'mid'
18            long long hoursNeeded = 0;
19            for (int pile : piles) {
20                // Equivalent to ceil(pile / mid)
21                hoursNeeded += (pile + mid - 1) / mid; 
22            }
23            
24            if (hoursNeeded <= h) {
25                // Speed is sufficient, try to find a smaller speed
26                result = mid;
27                right = mid - 1;
28            } else {
29                // Speed is too slow, increase it
30                left = mid + 1;
31            }
32        }
33        
34        return result;
35    }
36};

Java Solution for LeetCode 875

1class Solution {
2    public int minEatingSpeed(int[] piles, int h) {
3        int left = 1;
4        int right = 0;
5        
6        // Determine the upper bound
7        for (int pile : piles) {
8            right = Math.max(right, pile);
9        }
10        
11        int result = right;
12        
13        while (left <= right) {
14            int mid = left + (right - left) / 2;
15            
16            long hoursNeeded = 0;
17            for (int pile : piles) {
18                // Integer arithmetic for ceil(pile / mid)
19                hoursNeeded += (pile + mid - 1) / mid;
20            }
21            
22            if (hoursNeeded <= h) {
23                result = mid;
24                right = mid - 1;
25            } else {
26                left = mid + 1;
27            }
28        }
29        
30        return result;
31    }
32}

Python Solution for LeetCode 875

1import math
2
3class Solution:
4    def minEatingSpeed(self, piles: List[int], h: int) -> int:
5        left = 1
6        right = max(piles)
7        
8        def can_finish(k):
9            hours_needed = 0
10            for pile in piles:
11                # Calculate ceiling of pile / k
12                hours_needed += (pile + k - 1) // k
13            return hours_needed <= h
14        
15        while left <= right:
16            mid = (left + right) // 2
17            
18            if can_finish(mid):
19                # Valid speed, try smaller
20                right = mid - 1
21            else:
22                # Too slow, need higher speed
23                left = mid + 1
24                
25        return left