Koko Eating Bananas

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the $i^{th}$ 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.

Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23

Approach: Binary Search on Answer

This is a classic “Binary Search on Answer” problem. Instead of searching for an element in an array, we are searching for the optimal value in a known numerical range.

We know the eating speed k must fall within a specific range:

• Minimum possible speed: 1 banana per hour.
• Maximum possible speed: The maximum number of bananas in any single pile (Math.max(...piles)). Eating faster than the largest pile doesn’t save any extra time because Koko can only eat from one pile per hour.

Because the total time it takes to eat all bananas monotonically decreases as the speed k increases, we can binary search the optimal k.

1. Initialize left = 1 and right = Math.max(...piles).
2. Keep track of the minimum valid speed found so far in a variable res (initialized to right).
3. Loop while left <= right:
   • Calculate k = Math.floor((left + right) / 2). This is our current guess for the eating speed.
   • Calculate the total hours it would take to eat all piles at speed k. For each pile, the hours needed is Math.ceil(pile / k).
   • If totalHours <= h: Koko can successfully finish in time at speed k. We record res = Math.min(res, k) and try to find an even smaller speed by searching the left half: right = k - 1.
   • If totalHours > h: Koko cannot finish in time. She needs to eat faster, so we search the right half: left = k + 1.
4. Return res.

Solution

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
function minEatingSpeed(piles, h) {
    let left = 1;
    let right = Math.max(...piles);
    let res = right;
    
    while (left <= right) {
        const k = Math.floor((left + right) / 2);
        
        let totalHours = 0;
        for (let i = 0; i < piles.length; i++) {
            totalHours += Math.ceil(piles[i] / k);
        }
        
        if (totalHours <= h) {
            res = Math.min(res, k);
            right = k - 1; // Try to find a smaller valid speed
        } else {
            left = k + 1; // Speed is too slow, must eat faster
        }
    }
    
    return res;
}

Complexity Analysis

• Time Complexity: $O(n \log(\max(P)))$ where $n$ is the number of piles and $\max(P)$ is the maximum size of a pile in the piles array. The binary search takes $O(\log(\max(P)))$ steps, and for each step, we iterate over the $n$ piles to calculate the total hours, which takes $O(n)$ time.
• Space Complexity: $O(1)$. We only use a few variables (left, right, k, totalHours, res), so the space complexity is constant.