Koko Eating Bananas (Minimum Rate)¶

Question¶

A monkey has \(n\) piles of bananas. In one hour, she can eat \(k\) bananas from a pile. If the pile has fewer than \(k\), she finishes the pile and waits until the next hour. Given \(h\) hours, find the minimum integer \(k\) such that she can finish all bananas.

Solution¶

Pattern¶

Binary Search on Answer Space

How to Identify¶

The goal is to minimize a value (\(k\)).
The search space is monotonic: If Koko can finish at speed \(10\), she can definitely finish at speed \(11\). If she can't finish at \(10\), she definitely can't at \(9\).
We have a clear range for the answer: \([1, \max(piles)]\).

Description¶

We binary search for the speed \(k\). For each mid, we calculate the total hours required by summing the ceiling of pile / mid.

If totalHours <= h: The speed is valid. Record it as a candidate and try to find a smaller one (right = mid - 1).
If totalHours > h: The speed is too slow. Increase it (left = mid + 1).

The Intuition¶

Imagine a treadmill speed. If you set it to \(10\) mph and finish your run in time, you ask, "Could I have gone slower and still finished?" You drop the speed and check. If you set it to \(2\) mph and fail, you know you must go faster.

Complexity¶

Time Complexity: \(O(n \cdot \log(\max(piles)))\)
Space Complexity: \(O(1)\)

Code¶

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) right = Math.max(right, pile);

        int result = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (canFinish(piles, mid, h)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private boolean canFinish(int[] piles, int speed, int h) {
        long totalHours = 0;
        for (int pile : piles) {
            // Integer Ceiling: (a + b - 1) / b
            totalHours += (pile + (long)speed - 1) / speed;
        }
        return totalHours <= h;
    }
}

Concepts to Think About¶

The h == piles.length Case: In this case, the answer is always max(piles) because she needs at least one hour per pile.
Large h: If h is much larger than the total number of bananas, the answer is 1.
Floating Point Precision: Why not use Math.ceil((double)pile / speed)? Aside from performance, casting large long values to double can lose precision, leading to incorrect results for very large piles.

Logical Follow-up¶

Question: "If Koko could eat from multiple piles in the same hour as long as she doesn't exceed k total bananas, how would the problem change?"

Solution: The problem would become much simpler. You would just need to find ⌈(∑piles)/h⌉. The restriction of "one pile per hour" is what makes the binary search necessary.

Question: "What if Koko is picky and will only eat from a pile if it has an even number of bananas? How does your canFinish function change?"

Solution: You would add an if (pile % 2 == 0) check inside the loop. However, you must ask the interviewer: "Does she skip the odd piles entirely, or does she eat the even portion and leave 1 banana?" This clarifies the requirements phase of the interview.

Question (The Distributed Koko): "Imagine the piles array is so massive it is stored across 1,000 different machines in a Google Data Center. You cannot fit the array in one machine's memory. How do you find the minimum \(k\)?"

L5 Analysis & Solution:

MapReduce Approach: The Binary Search still happens on a "Master" node because \(\log(10^9)\) is only 30 iterations.
Worker Nodes: For each iteration, the Master broadcasts the current mid (speed) to all 1,000 Worker nodes.
Local Summation: Each worker calculates the totalHours for its local slice of piles.
Reduce: The Master sums the 1,000 partial results and compares them to h.
Network Bottleneck: Mention that the bottleneck here isn't the CPU; it's the network latency of broadcasting the mid and collecting the results. You might optimize by having workers skip the calculation if mid hasn't changed significantly.