2.2 Binary Search on Answer

Demo: Koko Eating Bananas — LC 875 (Medium — Amazon/Google High)

Statement (Demo): There are n piles with piles[i] bananas. Every hour Koko eats up to k bananas from one pile (a smaller pile is finished whole). Return the minimum k that lets her finish within h hours. Example: piles=[3,6,7,11], h=8 → 4 | ⚡ n ≤ 10⁴, 1 ≤ piles[i] ≤ 10⁹, n ≤ h ≤ 10⁹

Approach: Search the answer space, not the array: speed from 1 to max(piles). canFinish(k) is monotonic, so binary search for the smallest feasible k.

function minEatingSpeed(piles, h) {
  const canFinish = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h;
  let lo = 1,
    hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canFinish(mid))
      hi = mid; // try a smaller speed
    else lo = mid + 1;
  }
  return lo;
}

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