#875 - Koko Eating Bananas

MediumBinary Search

Koko has piles of bananas and h hours. She eats at speed k bananas/hour (one pile at a time, even if k exceeds the pile). Return the minimum k such that she can eat all bananas within h hours.

Input	Output
piles = [3,6,7,11], h = 8	4
piles = [30,11,23,4,20], h = 5	30
piles = [30,11,23,4,20], h = 6	23

Solution Space

Try it

/**
 * Finds the minimum eating speed k so Koko finishes all piles in h hours.
 * Binary search over k in [1, max(piles)].
 *
 * @param piles Array of pile sizes
 * @param h     Total hours available
 * @returns     Minimum eating speed
 */
export function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = Math.max(...piles);

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);

    // Hours needed at speed mid
    const hours = piles.reduce((sum, pile) => sum + Math.ceil(pile / mid), 0);

    if (hours <= h) {
      hi = mid; // feasible → try smaller speed
    } else {
      lo = mid + 1; // too slow → need faster
    }
  }

  return lo;
}

Approach: binary search on answer – the search space is the eating speed `[1, max(piles)]`. For each candidate speed, compute total hours and check feasibility.

Time: O(n · log(max(piles))) – n piles checked per binary search step.

Space: O(1) – only a few variables.

#374 Guess Number Higher or Lower

#2300 Successful Pairs of Spells and Potions