THE WHY BEHIND EVERY DSA PROBLEM
SHEET: STRIVER A2Z · REV 0.1
UNDERSTOOD: 0 / 79 DRAFTED
STEP 4 · BINARY SEARCH · BS ON ANSWER · MEDIUM

Koko Eating Bananas

WHAT IT SAYS

Find the minimum eating speed to finish all piles in h hours.

WHAT IT'S REALLY ASKING

"The answers form a line of no, no, no, yes, yes, yes — can you see the array hiding in that?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Brute force: try every speed

O(max(pile) · n) time

Test k = 1, 2, 3, … until one finishes in time. Each test simulates all the piles.

WHERE THE WORK IS WASTED — If speed k succeeds, every speed above k succeeds too. You're walking a sorted sequence of yes/no answers one at a time — the exact situation linear search exists to be replaced in.

!
KEY OBSERVATION — THE UNLOCKlink

Feasibility is monotonic, so the answer space is searchable.

"Can Koko finish at speed k?" flips from false to true exactly once and never flips back. Any monotone yes/no sequence can be binary searched — even when it isn't an array in memory, just a range of candidate answers. The array was imaginary all along; binary search never cared.

Binary search the answer space

O(n · log max(pile)) time

Search k in [1, max(pile)]. Midpoint feasible → the boundary is at mid or left of it. Infeasible → it's right of mid. The feasibility check is a cheap O(n) simulation.

WHAT YOU TRADED — The mental unlock: binary search needs monotonicity, not an array. Once you hear "minimum x such that check(x) passes," the container is irrelevant.
WATCH THE IDEA RUN
THE PILES (never searched)
3
0
6
1
7
2
11
3
THE ANSWER SPACE — speeds 1..11. THIS is the sorted array.
1
0lo
2
1
3
2
4
3
5
4
6
5
7
6
8
7
9
8
10
9
11
10hi
search window [1, 11]
speeds actually evaluated 0 / 11
answer …
There is no sorted array here. There are piles, and a question about speed. So what exactly would you binary search?
step 1 / 7
THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Binary Search on the Answer

YOU'LL SEE IT AGAIN WHEN

  • "Minimum speed / capacity / days such that…"
  • A cheap check(x) that is monotone in x
  • The answer lives in a numeric range, not at an index

SAME BLUEPRINT, DIFFERENT PROBLEM

Ship Packages in D DaysSplit Array Largest SumAggressive Cows
The bar isn't "solved it once." It's "could rebuild it from the observation."