30. Koko Eating Bananas

MediumArray Binary Search

Koko the monkey has found piles.length piles of bananas; pile i holds piles[i] bananas. The keepers return in h hours.

Koko picks an integer eating speed k (bananas per hour). Every hour she chooses one pile and eats k bananas from it. If that pile has fewer than k left, she finishes it and waits out the rest of the hour without starting another pile.

Return the smallest k that lets her finish every pile within h hours.

Example 1

Input: piles = [4,9,5,12], h = 7
Output: 5

Explanation: At speed 5 the piles take 1 + 2 + 1 + 3 = 7 hours. At speed 4 they would take 1 + 3 + 2 + 3 = 9 hours, which is too slow.

Example 2

Input: piles = [20,11,7], h = 3
Output: 20

Explanation: With one hour per pile she must clear the largest pile in a single hour.

Example 3

Input: piles = [6,6,6], h = 9
Output: 2

Constraints

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

💡 Hint 1

For a fixed speed k, the time for one pile is ceil(pile / k), so checking a single speed takes O(n).

💡 Hint 2

If speed k is fast enough, every faster speed is too. That monotonic yes/no answer can be binary searched.

💡 Hint 3

The answer lies between 1 and max(piles). Watch out for overflow when adding up hours in Java.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Binary search on the answer. Whether speed k works is monotonic: a faster speed never needs more hours. So search k in [1, max(piles)], where the upper bound always works because each pile then takes one hour. For a candidate mid, add up ceil(p / mid) over all piles (Java can use the integer form (p - 1) / mid + 1). If the total fits in h, mid is feasible and the answer is mid or smaller (hi = mid); otherwise it is too slow (lo = mid + 1). In Java the running total can exceed int range, so accumulate it in a long.

Time O(n log m), where m = max(piles)Space O(1)

function minEatingSpeed(piles, h) {
  let lo = 1;
  let hi = Math.max(...piles);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / mid);
    if (hours <= h) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1, hi = 0;
        for (int p : piles) hi = Math.max(hi, p);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long hours = 0;
            for (int p : piles) hours += (p - 1) / mid + 1;
            if (hours <= h) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
function minEatingSpeed(piles, h) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit