Problem: Koko Eating Bananas (Search on Answer)

Problem Statement

Koko loves to eat bananas. There are n piles of bananas. Koko can decide her eating speed of k bananas per hour. She wants to finish all bananas within h hours.

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

Approach: Search on Answer

The "Answer" (speed $k$) has a monotonic property:

• If speed $k$ is sufficient, any speed $> k$ is also sufficient.
• If speed $k$ is insufficient, any speed $< k$ is also insufficient.

1. Define Range: The minimum speed is 1, and the maximum speed is the largest pile.
2. Binary Search:
   • Pick a middle speed mid.
   • Calculate the total hours needed at speed mid.
   • If totalHours <= h: mid might be the answer, but try smaller speeds (right = mid).
   • Else: speed is too slow, try larger speeds (left = mid + 1).

Java Implementation

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = 0;
    for (int p : piles) right = Math.max(right, p);
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(piles, h, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean canEatAll(int[] piles, int h, int speed) {
    long time = 0;
    for (int p : piles) {
        time += (p + speed - 1) / speed; // Ceiling division
    }
    return time <= h;
}

Complexity Analysis

• Time Complexity: $O(n \log (\max(piles)))$. We binary search over the range of speeds.
• Space Complexity: $O(1)$.

Interview Tips

• Mention why we use long for time: "To prevent integer overflow if h is large."
• Explain ceiling division: (a + b - 1) / b is a clean way to write ceil(a/b) in Java.