Binary Search crash course ↗ · 27

875. Koko Eating Bananas

Koko must finish all piles in h hours — find the minimum eating speed. The answer space [1, max(piles)] is sorted by feasibility, so a single binary search on the answer finds it in O(n log m) time.

● MediumBinary Search on the AnswerFeasibility CheckTypeScript

PROBLEM What we're solving

Given piles of bananas piles and a guard arrival time h (in hours), Koko eats at most k bananas per hour from one pile per hour. Return the minimum integer k such that she can finish every pile within h hours.

Worked example: piles = [3, 6, 7, 11], h = 8. At speed k = 4: pile 3 → 1 h, pile 6 → 2 h, pile 7 → 2 h, pile 11 → 3 h — total 8 h ✓. At k = 3: pile 11 alone needs 4 h; total = 10 h > 8 ✗. Answer: 4.

KEY IDEA Search the answer space, not the input

Insight → the function feasible(k)= "can Koko finish all piles at speed k in ≤ h hours?" is monotonically non-decreasing: once some speed works, every larger speed also works. That monotonicity is exactly the precondition for binary search — so binary-search on k directly rather than on any array index.

RECIPE Binary-search the minimum feasible speed

  • 0 · Fix the search space. The slowest possible speed that always works is max(piles) (one hour per pile). The fastest valid minimum is 1. Search in [1, max(piles)].
  • 1 · Check feasibility at mid. Count total hours at speed mid: sum(⌈pile / mid⌉ for pile in piles). This is O(n).
  • 2 · Shrink the window. If hours <= h, mid is feasible — record it and try slower (hi = mid). Otherwise mid is too slow — try faster (lo = mid + 1).
  • 3 · Return lo. When lo === hi the window has collapsed to exactly the minimum feasible speed.
Classic confusion → whether to write hi = mid or hi = mid - 1 when feasible. Because we want the minimum speed and mid itself might be the answer, set hi = mid (keep mid in the window). Use the lo < hi loop form — it terminates with lo === hi without an off-by-one.

COST Complexity & alternatives

Linear scan all speeds
O(n · m)
Try every k from 1 to max(piles); feasibility check is O(n) each.
Binary search on k
O(n log m)
log(max(piles)) probes × O(n) feasibility. m = max(piles).

Space is O(1) — only a handful of pointers. The feasibility check itself is pure arithmetic; no sorting or extra allocation needed.

Pattern transfer → "binary search on the answer" recurs widely: Capacity To Ship Packages Within D Days (same feasibility skeleton), Find Minimum in Rotated Sorted Array (search a monotone property on an array), Split Array Largest Sum (minimize the maximum subarray sum), and Kth Smallest in a Matrix. Whenever the answer lives in a sorted value space and you can check "is X feasible?" in sub-quadratic time, binary search the answer.

RUN IT Binary search the minimum eating speed

step 0 / 9
STARTPiles: [3, 6, 7, 11], h = 8. Binary search speed k in [1, 11].
1function minEatingSpeed(piles: number[], h: number): number {
2▶  let lo = 1;
3▶  let hi = Math.max(...piles);   // max pile is a safe upper bound
4 
5  while (lo < hi) {              // invariant: answer is in [lo, hi]
6    const mid = (lo + hi) >> 1;
7    const hours = piles.reduce((s, p) => s + Math.ceil(p / mid), 0);
8 
9    if (hours <= h) {
10      hi = mid;                  // mid is feasible — try slower (smaller k)
11    } else {
12      lo = mid + 1;              // mid is too slow — need faster k
13    }
14  }
15 
16  return lo;                     // lo === hi: the minimum feasible speed
17}
piles =36711
State
1
lo
11
hi
—
mid
—
hours
11
ans
lo boundaryhi boundaryfeasible / answerinfeasible
slowfast

TYPESCRIPT The solution, annotated

kokoEatingBananas.ts
function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = Math.max(...piles);   // max pile is a safe upper bound

  while (lo < hi) {              // invariant: answer is in [lo, hi]
    const mid = (lo + hi) >> 1;
    const hours = piles.reduce((s, p) => s + Math.ceil(p / mid), 0);

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

  return lo;                     // lo === hi: the minimum feasible speed
}

Reading it block by block

Lines 2–3 — fix the search space. Speed 1 is the absolute minimum (always feasible given enough time). Math.max(...piles) is the safe upper bound because at that speed every pile takes exactly 1 hour. Any answer must live in this range.
Line 5 — loop invariant. lo < hikeeps the loop running until the window collapses to a single value. The invariant is "the true minimum feasible speed is always in [lo, hi]".
Lines 6–7 — probe and feasibility check. mid = (lo + hi) >> 1 avoids overflow. The feasibility check sums ⌈pile / mid⌉ for every pile — how many hours pile p takes at speed mid. Total time is O(n) per probe.
Lines 9–12 — shrink the window. If feasible (hours <= h), hi = mid keeps mid in the window because it might be the minimum. If infeasible, lo = mid + 1 discards midentirely — it's confirmed too slow.
Line 15 — return lo. The loop exits with lo === hi. That single remaining value is the minimum eating speed.
Complexity → O(n log m) time — the binary search runs O(log m) iterations (m = max(piles) ≤ 10⁹ ≈ 30 iterations) and each feasibility check is O(n). Space is O(1).

INTERVIEWFollow-ups they'll ask

  • "What if piles can be zero?" Guard against division by zero in the ceiling: skip zero-sized piles or clamp lo to 1 (the problem guarantees piles[i] ≥ 1, but confirm constraints).
  • "Return the actual schedule, not just the speed?" After finding k, iterate piles and assign each to the next ⌈pile/k⌉ consecutive hours.
  • "What if h < piles.length?" Impossible — Koko eats from one pile per hour, so she needs at least piles.length hours. Return -1 or throw as appropriate.
  • "Can you solve it without binary search?" Yes — linear scan from 1 to max(piles) is O(n · m). Binary search reduces this to O(n log m), which matters when pile values are large (up to 10⁹ per the real constraints).
  • "Variant: minimize the number of hours instead?" That flips the optimization direction — binary search on h instead of k, or just use k = max(piles) and sum the ceiling hours.

OPTIMAL Binary Search on the Answer

kokoEatingBananas.ts
function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = Math.max(...piles);   // max pile is a safe upper bound

  while (lo < hi) {              // invariant: answer is in [lo, hi]
    const mid = (lo + hi) >> 1;
    const hours = piles.reduce((s, p) => s + Math.ceil(p / mid), 0);

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

  return lo;                     // lo === hi: the minimum feasible speed
}
Complexity → O(n log m) time — the binary search runs O(log m) iterations (m = max(piles) ≤ 10⁹ ≈ 30 iterations) and each feasibility check is O(n). Space is O(1).

ALT 1 Brute force — try every speed from 1 upward

O(m · n) time · O(1) space

Speeds are monotone — faster always finishes no later. So just test k = 1, 2, 3, … and return the first speed whose total hours fit in h. Here m is the largest pile.

approach-2.ts
function minEatingSpeed(piles: number[], h: number): number {
  const max = Math.max(...piles);

  for (let k = 1; k <= max; k++) {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);
    if (hours <= h) return k;     // first feasible speed is the minimum
  }

  return max;                     // worst case: eat the biggest pile per hour
}
Note → Scanning up to m candidate speeds, each an O(n) feasibility check, is O(m·n) and m can be 10⁹. Because feasibility is monotone in k, binary-searching the speed range turns the O(m) scan into O(log m).

MNEMONIC The one-liner

"Search the speed, not the piles — if you can finish at k, try slower; if you can't, go faster."

TRIGGERS When you see ___ → reach for ___

"minimum speed / capacity / rate to finish in D days"binary search on the answer
feasible(x) is monotone (once true, stays true)binary search the threshold
⌈a / b⌉ ceiling division in integer mathMath.ceil(a / b) or (a + b - 1) / b | 0
want minimum-of-maximums or maximum-of-minimumsbinary search + feasibility check

SKELETON The reusable shape

skeleton.ts
function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1;
  let hi = Math.max(...piles);

  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    const hours = piles.reduce((s, p) => s + Math.ceil(p / mid), 0);
    if (hours <= h) hi = mid;
    else lo = mid + 1;
  }

  return lo;
}

FLASHCARDS Tap to flip

Why can we binary search on k (the eating speed)?
feasible(k) is monotone — if k works, k+1 also works. Binary search needs exactly this sorted yes/no structure.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
For piles = [3, 6, 7, 11], h = 8, the answer is:
QUESTION 02
What is the time complexity of the optimal solution?
QUESTION 03
When the feasibility check passes (hours <= h), why do we set hi = mid rather than hi = mid - 1?
QUESTION 04
What is the correct upper bound for the binary search?
QUESTION 05
The loop condition is lo < hi (not lo <= hi). What value does the function return?
QUESTION 06
Koko finishes pile p at speed k in how many hours?
QUESTION 07
Which sibling problem uses the same binary-search-on-answer pattern?
QUESTION 08
#875 · Koko Eating BananasBinary search on the eating speed k from 1 to max(piles). Feasibility — can Koko finish all piles in h hours at speed k — is monotone, so the minimum feasible k is found in O(n log max).Which algorithmic approach does this primarily use?
QUESTION 09
#875 · Koko Eating BananasBinary search on the eating speed k from 1 to max(piles). Feasibility — can Koko finish all piles in h hours at speed k — is monotone, so the minimum feasible k is found in O(n log max).Which implementation correctly solves it?