Typorithm · medium

Koko Eating Bananas

koko-eating-bananasbinary-search-answeranswer-spacefeasibilityminimize

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Koko Eating Bananas

Binary Search on Answer

Binary search the eating speed; a speed is feasible if total hours <= h, and we shrink toward the minimum feasible speed.

The answer is a speed between 1 and the largest pile, and feasibility is monotonic — faster always works if slower does.

Binary search the speed; for each candidate, sum ceil(pile / speed) hours.

If it fits in h hours, search lower; otherwise search higher, converging on the minimum feasible speed.

Search the speed, not the piles.

Feasible: total hours <= h.

Shrink hi toward the minimum.

function minEatingSpeed(piles, h) {
  let lo = 1;
  let hi = Math.max(...piles);

  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / mid);
    }
    if (hours <= h) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }

  return lo;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Speed bounds

The slowest useful speed is 1; the fastest needed is the biggest pile.

let hi = Math.max(...piles)

2. Candidate speed

Binary search the speed, not the array.

const mid = (lo + hi) >> 1

3. Hours at speed

Each pile takes ceil(pile / speed) hours.

hours += Math.ceil(pile / mid)

4. Fast enough

If she finishes in time, try a slower speed.

if (hours <= h) {
      hi = mid;
    }

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.