Koko Eating Bananas

medium binary search answer search

Problem

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

Inputpiles = [3, 6, 7, 11], H = 8

Output4

Rate 4 takes ⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 hours.

piles (positive integers)

H (hours)

def min_eating_speed(piles, H):
    def can(r): return sum((p + r - 1) // r for p in piles) <= H
    l, r = 1, max(piles)
    while l < r:
        m = (l + r) // 2
        if can(m): r = m
        else: l = m + 1
    return l

function minEatingSpeed(piles, H) {
  const can = r => piles.reduce((s, p) => s + Math.ceil(p / r), 0) <= H;
  let l = 1, r = Math.max(...piles);
  while (l < r) {
    const m = (l + r) >> 1;
    if (can(m)) r = m; else l = m + 1;
  }
  return l;
}

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int max = 0; for (int p : piles) if (p > max) max = p;
        int l = 1, r = max;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (canEat(piles, m, H)) r = m; else l = m + 1;
        }
        return l;
    }
    private boolean canEat(int[] piles, int rate, int H) {
        long s = 0; for (int p : piles) s += (p + rate - 1) / rate;
        return s <= H;
    }
}

bool canEat(vector<int>& piles, int rate, int H) {
    long long s = 0; for (int p : piles) s += (p + rate - 1) / rate;
    return s <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
    int l = 1, r = *max_element(piles.begin(), piles.end());
    while (l < r) {
        int m = (l + r) / 2;
        if (canEat(piles, m, H)) r = m; else l = m + 1;
    }
    return l;
}

Explanation

We want the slowest eating speed that still finishes all piles within H hours. Trying every speed would be slow, so we binary-search on the answer: the speed itself.

The key insight is monotonicity: if some speed r is fast enough, every speed above it is too, and every speed below might not be. The helper can(r) computes the hours needed as sum(ceil(p / r)) over the piles and checks it is <= H. That makes a clean "no, no, …, yes, yes" pattern to bisect.

The range is [1, max(piles)] — eating faster than the biggest pile never helps. When can(mid) is true we try slower with r = mid; when false we must go faster with l = mid + 1. The loop lands on the smallest feasible speed.

Example: piles = [3,6,7,11], H = 8. Speed 4 takes 1+2+2+3 = 8 hours, which fits, while speed 3 needs more than 8. So the slowest workable speed is 4.

Each feasibility check is O(n) and the search does O(log max) of them, giving O(n log max) overall.

Time: O(n log max) Space: O(1)