Koko Eating Bananas

MediumArray Binary Search

Koko, a gorilla at a wildlife sanctuary, gets her daily bananas in piles: pile i holds piles[i] bananas. The keepers have h hours before the enclosure has to be cleared. Eating too quickly upsets Koko's stomach, so they want the slowest steady pace that still gets every banana eaten in time.

A pace is a whole number k of bananas per hour. Each hour, Koko picks one pile and eats k bananas from it. If that pile has fewer than k left, she finishes it and rests for the rest of the hour rather than starting on another pile.

Return the smallest pace k that finishes all the piles within h hours. Every test allows at least one hour per pile, so some pace always works.

Example 1

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

Explanation: At 4 bananas per hour the piles take 3 + 1 + 2 = 6 hours. At 3 per hour they would take 4 + 1 + 3 = 8, which is too long.

Example 2

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

Explanation: With exactly one hour per pile, Koko has to finish the biggest pile in a single hour.

Example 3

Input: piles = [1,1,1], h = 100
Output: 1

Explanation: Even the slowest possible pace finishes in 3 hours.

Constraints

There are between 1 and 10^4 piles.
Each pile holds between 1 and 10^9 bananas.
h is at least the number of piles and at most 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