Koko eating bananas

Problem Link

koko-eating-bananas

Problem Statement

Koko loves eating bananas. She is given an array piles where piles[i] represents the number of bananas in the i-th pile. The guards will return in h hours.

Each hour, Koko chooses a pile and eats up to k bananas from it. If the pile has fewer than k bananas, she eats all of them and waits for the next hour.

Koko wants to eat slowly but still finish all bananas before the guards return. Return the minimum integer k (bananas/hour) such that Koko can eat all the bananas within h hours.

Examples

• Input: piles = [3,6,7,11], h = 8
  Output: 4
  Explanation: At k = 4, Koko finishes all bananas in exactly 8 hours.

• Input: piles = [30,11,23,4,20], h = 5
  Output: 30
  Explanation: She must eat at full speed (30 bananas/hour) to finish on time.

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

Constraints

• 1 <= piles.length <= 10^4

• piles.length <= h <= 10^9

• 1 <= piles[i] <= 10^9

Intuition

This is a search over answer problem. We want to minimize k such that the total time to eat all piles at that speed is <= h.

Since time increases as k decreases (and vice versa), the function is monotonic. This allows us to use binary search to find the minimum feasible k.

Approach

1. Define the search range for k:

   • Minimum value: 1

   • Maximum value: max(piles) — the worst-case speed where Koko finishes a pile in one hour.

2. Apply binary search:

   • For each k = mid, simulate eating all piles and compute total hours required:

     hours = sum(ceil(pile / k) for each pile)
     

   • If hours <= h, k is feasible, try to find a smaller one → end = mid - 1

   • Else, try a higher speed → start = mid + 1

3. When the search ends, the smallest feasible speed is at start.

Java Code

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int start = 1;
        int end = Integer.MIN_VALUE;

        for (int pile : piles) {
            end = Math.max(end, pile); // max value in piles
        }

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (canEatAll(piles, h, mid)) {
                end = mid - 1; // try lower k
            } else {
                start = mid + 1; // increase k
            }
        }

        return start;
    }

    private boolean canEatAll(int[] piles, int h, int speed) {
        int hours = 0;
        for (int pile : piles) {
            hours += Math.ceil((double) pile / speed);
        }
        return hours <= h;
    }
}

Time and Space Complexity

• Time Complexity: O(n * log m)

  • log m is for binary search on speed range [1, max(piles)]

  • Each canEatAll() check takes O(n) where n = piles.length

• Space Complexity: O(1)

  • Constant space used.

Dry Run

Input:

piles = [3, 6, 7, 11], h = 8

Search Range:

start = 1, end = 11

• mid = 6, total hours = 1 + 1 + 2 + 2 = 6 → feasible → try lower → end = 5

• mid = 3, total hours = 1 + 2 + 3 + 4 = 10 → too much → start = 4

• mid = 4, total hours = 1 + 2 + 2 + 3 = 8 → feasible → try lower → end = 3

Loop ends: start = 4, so answer = 4

Conclusion

This problem is a textbook example of applying binary search on the answer space. The key insight is recognizing that the time to eat bananas is a monotonic function of the speed k, enabling an efficient O(n log m) solution.

The canEatAll() simulation is straightforward but must be optimized using integer math or Math.ceil() with proper casting to avoid errors.

This is a classic "minimize the maximum" problem and is commonly asked in system design and algorithmic rounds.