KOKO Eating Bananas

return k bananas koko can eat each hour to eat all the banans

Koko Eating Bananas

Problem

Koko loves bananas. There are n piles, and the ith pile has piles[i] bananas. The guards will come back in h hours.

Koko picks an eating speed of k bananas per hour. Each hour, she picks one pile and eats k bananas from it.

• If the pile has fewer than k bananas, she eats the whole pile.
• She does not eat from another pile in that same hour.

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

Examples

Example 1

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

• With k = 4, the hours needed are 1 + 2 + 2 + 3 = 8.
• With k = 3, the hours needed are 1 + 2 + 3 + 4 = 10, which is more than 8.

Example 2

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

• There are 5 piles and only 5 hours. So she must finish one pile per hour.
• The biggest pile has 30 bananas, so k = 30.

Example 3

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

• With k = 23, the hours needed are 2 + 1 + 1 + 1 + 1 = 6.

Constraints

• 1 <= piles.length <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

Main Idea

We do not know k, but we know the range where it must be.

• The smallest possible speed is 1.
• The biggest speed we ever need is max(piles). At this speed, each pile takes exactly 1 hour. Since h >= piles.length, this always works.

So k is in the range [1, max(piles)].

Why binary search works

The answer has a monotonic property:

• If speed k works, then any bigger speed also works.
• If speed k does not work, then any smaller speed also does not work.

So the speeds look like this:

speed:   1  2  3  4  5  6 ...
works?   N  N  N  Y  Y  Y ...

We want the first Y. This is a perfect case for binary search.

How to count hours for a speed

For one pile, the hours needed are Math.ceil(pile / k).

• Example: pile = 7, k = 3. Hours = ceil(7 / 3) = 3.

We add the hours of all piles. If the total is <= h, the speed works.

Steps

• Set l = 1 and r = max(piles).
• Find mid, and count the hours needed at speed mid.
• If hours <= h, mid works. Save it as ans, and try a smaller speed: r = mid - 1.
• Otherwise, mid is too slow. Try a bigger speed: l = mid + 1.
• When l > r, ans is the minimum speed.

Brute Force (For Comparison)

Try every speed from 1 up, and return the first one that works.

var minEatingSpeed = function (piles, h) {
    let max = 0;
    for (const pile of piles) {
        max = Math.max(max, pile);
    }

    for (let k = 1; k <= max; k++) {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / k);
        }

        if (hours <= h) {
            return k;
        }
    }
};

Complexity

• Time Complexity: O(n * m)
  • n is the number of piles and m is the biggest pile.
  • For each speed, we scan all piles.
  • m can be 10^9, so this is too slow.
• Space Complexity: O(1)
  • We use only a few variables.

Solution: Binary Search on the Answer

var minEatingSpeed = function (piles, h) {
    let l = 1;
    let r = Math.max(...piles);
    let ans = r;

    while (l <= r) {
        const mid = Math.floor((l + r) / 2);

        // hours needed at speed mid
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / mid);
        }

        if (hours <= h) {
            // mid works, save it and try a smaller speed
            ans = mid;
            r = mid - 1;
        } else {
            // mid is too slow, try a bigger speed
            l = mid + 1;
        }
    }

    return ans;
};

How the Code Works

Step 1: Set the search range

• l = 1 is the smallest speed.
• r = Math.max(...piles) is the biggest speed we need.
• ans = r is a safe starting answer, because this speed always works.

Step 2: Find the middle speed

• mid = Math.floor((l + r) / 2) is the speed we test now.

Step 3: Count the hours

• For each pile, Math.ceil(pile / mid) gives the hours for that pile.
• We add them into hours.

Step 4: Move the search range

• hours <= h: The speed works. We save it in ans. But a smaller speed may also work, so we search the left half with r = mid - 1.
• hours > h: The speed is too slow. We search the right half with l = mid + 1.

Step 5: Return the answer

• The loop ends when l > r.
• ans holds the smallest speed that worked.

Dry Run

Let us take piles = [3, 6, 7, 11] and h = 8.

The range is l = 1 and r = 11.

The answer is 4.

Complexity

• Time Complexity: O(n log m)
  • n is the number of piles and m is the biggest pile.
  • Binary search runs about log m times.
  • Each step counts the hours in O(n).
• Space Complexity: O(1)
  • We use only a few variables.

Tip: Math.max(...piles) is safe here, because n <= 10^4. For much bigger arrays, use a simple loop to find the max.

Comparison

Summary

• The answer k is between 1 and max(piles).
• If a speed works, every bigger speed also works. This lets us use binary search on the answer.
• For each speed, the hours needed are the sum of Math.ceil(pile / speed).
• If the hours are <= h, save the speed and search smaller. Otherwise, search bigger.
• The solution runs in O(n log m) time and uses O(1) space.