ONE COLLAPSE, EVERY ALGORITHM
YOUR CALL
The twist that unlocks the hardest binary-search problems: you are not searching the array, you are searching the answer. Pick a candidate, ask one yes/no question - is it feasible? - and because feasibility is monotone, binary search the boundary between no and yes.
This is not a list of problems. It is 8 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
8 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Every one of these searches a number, not an array. What the cards name is the check() you run at each guess — and recognising which check a statement is asking for is the whole skill of this deck.
the answer is a number, and you can test any guess
BINARY SEARCH THE ANSWER RANGE, not the inputO(n · log range)bigger is always easier — feasibility is monotone F…F T…T
MIN-FEASIBLE — find the first passing valueO(n · log range)guess the largest sum; a greedy pass counts the groups
MIN-MAX — Ship, Split Array, Painter's, Book AllocationO(n · log sum)the monotone quantity is a count, searched along the index
LOWER_BOUND on the derived count — Kth MissingO(log n)merging is O(m+n); the cut position is what you search
PARTITION SEARCH on the smaller arrayO(log min(m, n))the three ingredients: a range, a check(), and monotonicity
THIS WHOLE DECK — search the answerO(n · log range)The search space here is the ANSWER RANGE, and log tames it completely. Type a range size and the surviving row lights up.
log GROWS SO SLOWLY THE RANGE IS ALMOST FREE · ~60 CHECKS COVER 10¹⁸ · THE COST IS THE O(n) CHECK, NOT THE SEARCH
All 8 units, one reframe: search the answer. Sqrt introduces it; Koko is the archetype; Ship and Split Array are one min-max twice; Median is the partition apex.
A problem asks for the minimum value of something “such that” a condition holds, gives you a way to test any candidate, and has a huge search space. What is the shape?
Binary search on the answer. The tell is three things arriving together: the answer is a single number in a known range, you can check() any guess (often in O(n)), and feasibility is monotone — once a value works, everything on one side of it works too. That monotonicity is what turns “try every value” into “binary-search the boundary between fail and pass”. Miss any one of the three and it is a different technique; see all three and this is the default.
Why must the feasibility predicate check(x) be monotone for this technique to work?
Monotonicity is what makes a single check decisive. Binary search only works when testing the midpoint rules out an entire half — and that requires the verdicts to be sorted: all fails then all passes. If check could flip back and forth (F T F T), a pass at mid would tell you nothing about the values beyond it, and halving would be unsound. Before you binary-search an answer, the real work is proving the predicate is monotone — “if speed s finishes in time, so does any faster speed”.
This searches for the smallest feasible value but returns the largest instead. Which line is wrong?
while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (feasible(mid)) lo = mid + 1; // store & keep searching else hi = mid - 1; }
The move on a pass is backwards. To find the smallest value that works, a feasible mid means you have a candidate but should look for an even smaller one — so you go left: hi = mid - 1. Going right (lo = mid + 1) discards all the smaller feasible values and marches to the largest. The rule mirrors lower_bound: on a pass, record and keep going toward the boundary; on a fail, move away from it. Flip the direction and you solve the opposite problem.
This unit is the whole deck in one idea. Until now you searched an array; here there is no array to search — the answer is a number in a known range, and you binary-search that range directly. For floor(√x) the range is [1, x] and the test at each guess is mid·mid ≤ x: true for small guesses, false once you overshoot. Store the largest guess that still holds and reach higher; the boundary between holds and overshoots is the answer.
HOW DO YOU FIND A √ WITHOUT A LOOP OF 1, 2, 3, … — BY SEARCHING THE ANSWER?
In “binary search on the answer”, what plays the role the sorted array played in deck 1?
The range of candidate answers is the new search space. Deck 1 needed a sorted array so one comparison could discard a half; here the values 1, 2, …, x are already ordered, and the monotone check supplies the discarding power — if mid·mid ≤ x is false, every larger guess is false too. So you never materialise an array at all; you binary-search the number line, using check() where deck 1 used a[mid] < t.
Computing floor(√30) with lo=1, hi=30, the first mid is 15. What happens?
225 > 30, an overshoot. Since 15·15 already exceeds 30, every guess ≥ 15 does too, so the whole upper half is discarded: hi = 14. The search keeps halving — 7 overshoots, 3 holds (store it, go right), 5 holds (store), 6 overshoots — and settles on 5, because 5·5 = 25 ≤ 30 < 36 = 6·6. The strip on the MECHANISM slide shows the red (overshoot) and green (holds) regions closing in on the boundary.
This floorSqrt overflows and returns garbage for large x. Which line?
int mid = lo + (hi - lo) / 2; if (mid * mid <= x) // mid is int { ans = mid; lo = mid + 1; } else hi = mid - 1;
The product overflows a 32-bit int. When x is large, mid approaches ~46 340 and mid·mid crosses INT_MAX, wrapping to a negative value that is spuriously ≤ x — so the search charges past the real root. The fix is to compute the product as long (or compare with division: mid ≤ x / mid). It is the same overflow lesson as (lo+hi)/2, one level up: in answer-space search the arithmetic inside check() overflows before the indices do.
The reframe the whole deck turns on. There is no array to look through; the answer is a number in a known range, and you binary search that range directly. For floor(√x) the range is [1, x] and the test is mid·mid ≤ x — true for small guesses, false once you overshoot. Store the largest guess that still holds and reach higher. The array is gone; the number-line is the search space.
You are asked for a √, root, or floor of a root, or more generally the largest/smallest integer satisfying a numeric condition, with no array to search. The tell is that the answer itself is a number in a range and a guess can be checked in O(1). Reach for binary search on that range, not a loop from 1.
The value floor(√x) lives in [1, x]. For any guess mid, mid·mid ≤ x is true for small guesses and false once you overshoot — monotone. Store the largest guess that still holds and search right for a bigger one; when the interval empties, the stored value is the floor.
// Binary search the ANSWER: floor(sqrt(x)) is a number in [1, x]. // check(mid) = "mid*mid <= x" is true then false — monotone — so we // keep the largest guess that still fits under x. long avoids overflow. long floorSqrt(int x) { long lo = 1, hi = x, ans = 0; while (lo <= hi) { long mid = lo + (hi - lo) / 2; if (mid * mid <= x) { ans = mid; lo = mid + 1; } // fits: go bigger else hi = mid - 1; // overshoot } return ans; }
// Binary search the ANSWER: floor(sqrt(x)) is a number in [1, x]. // check(mid) = "mid*mid <= x" is true then false - monotone - so we // keep the largest guess that still fits under x. long avoids overflow. public long floorSqrt(int x) { long lo = 1, hi = x, ans = 0; while (lo <= hi) { long mid = lo + (hi - lo) / 2; if (mid * mid <= x) { ans = mid; lo = mid + 1; } // fits: go bigger else hi = mid - 1; // overshoot } return ans; }
# Binary search the ANSWER: floor(sqrt(x)) is a number in [1, x]. # check(mid) = "mid*mid <= x" is true then false, so keep the largest # guess that still fits. (Python ints don't overflow, but the shape is # the same as the C++ 'use long' habit.) def floor_sqrt(x): lo, hi, ans = 1, x, 0 while lo <= hi: mid = lo + (hi - lo) // 2 if mid * mid <= x: # fits under x: store and go bigger ans, lo = mid, mid + 1 else: hi = mid - 1 # overshoot: shrink return ans
Computing mid·mid in a 32-bit int. For large x, mid nears 46 340 and the square overflows INT_MAX, wrapping negative and passing the ≤ x test spuriously — the search then overshoots the true root. Use a 64-bit product, or compare as mid ≤ x / mid. In answer-space search the arithmetic inside the check overflows long before the bounds do.
The walkthrough for #01 Sqrt(x). Watch it, then go straight back and write it yourself.
The archetype every later problem imitates. Koko's answer — an eating speed — lives in [1, max pile]. For any speed you can check it: the hours needed are Σ ⌈pile / speed⌉, and you compare that to the budget H. Faster always means fewer (or equal) hours, so feasibility is monotone F…F T…T, and you binary-search the boundary — the slowest speed that still finishes in time. Range, a monotone check(), the smallest passing value: that triple is the entire pattern.
HOW DO YOU FIND THE SLOWEST SPEED THAT STILL BEATS THE DEADLINE?
Why is Koko's feasibility predicate monotone, and why does that matter?
More speed ⇒ never more hours, so the verdicts are sorted. Eating faster can only reduce (or hold) the hours for every pile, so once some speed s finishes within H, every speed above s does too — the pass/fail pattern is F…F T…T. That monotonicity is exactly what lets one test at mid discard a whole half. Without proving it you have no right to binary-search; with it, finding the slowest feasible speed is just lower_bound over the speed range.
Piles [3, 6, 7, 11], H = 8. Is speed 4 feasible?
Exactly 8 hours — feasible, and in fact the answer. ⌈3/4⌉=1, ⌈6/4⌉=2, ⌈7/4⌉=2, ⌈11/4⌉=3, summing to 8, which meets H=8. Speed 3 would need 1+2+3+4 = 10 > 8, so 3 fails — 4 is the boundary, the slowest speed that still finishes. The search visits 6 (feasible, go left), 3 (fails, go right), 4 (feasible) and stops. In PREDICT mode you compute those hours in your head before the panel reveals them.
Smallest Divisor Given a Threshold asks for the min d with Σ⌈a[i]/d⌉ ≤ threshold. How much of Koko do you reuse?
It is Koko with the words swapped. The divisor plays the role of the speed, Σ⌈a[i]/d⌉ plays the role of the hours, and the threshold plays the role of H; a bigger divisor shrinks the sum just as a bigger speed shrinks the hours, so it is the same monotone min-feasible search over [1, max(a)]. Seeing that two problems are one check() apart — and being unsurprised — is precisely the fluency this deck is built to produce.
The archetype. The answer — an eating speed — lives in [1, max pile]. For any guess you can check it: sum ⌈pile / speed⌉ and compare to the hour budget. Faster is always easier, so the verdicts are monotone F…F T…T and you binary search the boundary — the slowest speed that still finishes in time. The whole family is this: a range, and a monotone check().
“Minimum speed / rate such that a total (hours, work, cost) stays within a budget.” A rate you can test in O(n), a budget to meet, and “minimum … such that” — the canonical answer-space signal. Koko is the problem every later one in this deck imitates.
The speed lives in [1, max pile]. check(s) = Σ ⌈pile / s⌉ hours; faster never needs more hours, so hours ≤ H is false for slow speeds and true for fast ones. Binary-search the smallest speed that passes: on a feasible mid, store it and look left for an even slower one.
// Binary search the ANSWER (a speed) in [1, max pile]. A bigger speed // never needs more hours, so feasibility is monotone F...F T...T and we // hunt the smallest speed that still finishes within H hours. int minEatingSpeed(vector<int>& piles, int H) { int lo = 1, hi = *max_element(piles.begin(), piles.end()); while (lo <= hi) { int mid = lo + (hi - lo) / 2; long hours = 0; for (int p : piles) hours += (p + mid - 1) / mid; // ceil(p/mid) if (hours <= H) hi = mid - 1; // fits: try slower else lo = mid + 1; // too slow: speed up } return lo; }
// Binary search the ANSWER (a speed) in [1, max pile]. A bigger speed // never needs more hours, so feasibility is monotone F...F T...T and we // hunt the smallest speed that still finishes within H hours. public int minEatingSpeed(int[] piles, int H) { int lo = 1, hi = 0; for (int p : piles) hi = Math.max(hi, p); while (lo <= hi) { int mid = lo + (hi - lo) / 2; long hours = 0; for (int p : piles) hours += (p + mid - 1) / mid; // ceil(p/mid) if (hours <= H) hi = mid - 1; // feasible: try slower else lo = mid + 1; // too slow: speed up } return lo; // first feasible speed }
# Binary search the ANSWER (a speed) in [1, max pile]. Bigger speed # never needs more hours -> monotone -> smallest feasible speed wins. import math def min_eating_speed(piles, H): lo, hi = 1, max(piles) while lo <= hi: mid = lo + (hi - lo) // 2 hours = sum((p + mid - 1) // mid for p in piles) # ceil(p/mid) if hours <= H: hi = mid - 1 # fits: try slower else: lo = mid + 1 # too slow: speed up return lo
Summing the hours in a 32-bit int. With many large piles the hour total can exceed INT_MAX before you compare it to H, wrapping negative and making a too-slow speed look feasible. Accumulate in a long. The second slip is direction: on a feasible mid you go left (slower) — going right returns the fastest speed, not the slowest.
The walkthrough for #02 Koko Eating Bananas. Watch it, then go straight back and write it yourself.
Here the answer is a day. You need m bouquets, each made of k adjacent flowers that have bloomed. Later days mean more flowers have opened, so once a day is enough it stays enough — monotone. check(day) sweeps the garden, growing a run of adjacent bloomed flowers and cutting a bouquet every time the run reaches k. Binary-search the earliest feasible day over [min bloom, max bloom] — after first ruling out the impossible case m·k > n.
HOW DO YOU FIND THE EARLIEST DAY THAT YIELDS ENOUGH ADJACENT BOUQUETS?
Why must you check m·k ≤ n before the binary search even starts?
The predicate is false for the entire range, so the boundary does not exist. Binary search finds the first pass — but if m·k > n there is no pass at all, and a naive loop returns hi (the last day) as if it worked. Each bouquet consumes k flowers and they cannot be reused, so you simply need m·k flowers to exist. Guarding the impossible case up front is a general answer-space habit: confirm the range actually contains a feasible value before trusting the boundary.
bloom = [7,7,7,7,13,11,12,7], m=2, k=3. By day 11, how many bouquets can be cut?
Only one bouquet by day 11. Flowers with bloom day ≤ 11 are at indices {0,1,2,3,5,7} (index 6 blooms on day 12). The only run of k=3 adjacent indices is 0-1-2-3 → one bouquet; indices 5 and 7 are isolated, and 5-6-7 fails because 6 has not bloomed. So day 11 is infeasible and the search moves right; day 12 finally connects 5-6-7 for the second bouquet, making 12 the answer. Adjacency is why you cannot just count bloomed flowers.
What single change turns this into a valid answer-space problem versus an invalid one?
Monotonicity in the day is the licence to binary-search. Because a flower, once bloomed, stays bloomed, moving to a later day can only add flowers and therefore only increase the bouquets you can cut — so “can make m bouquets” flips from false to true exactly once. If wilting were possible (a flower bloomed then died) the predicate could flip back and the technique would be unsound. The lesson generalises: find the quantity that moves in one direction, and search on that.
The candidate is a day; later days mean more flowers have bloomed, so once you can cut m bouquets you always can — monotone again. check(day) walks the garden counting runs of k adjacent bloomed flowers. Binary search the earliest feasible day. First guard the impossible case: if m·k > n the answer is −1, because there simply aren't enough flowers.
“Minimum days / time until <something becomes possible>”, where waiting only helps. A day you can test, a monotone “more time ⇒ more available”, and a minimisation — answer-space over the time axis. The adjacency constraint is what makes the check non-trivial.
Guard the impossible case first: if m·k > n, return −1. Else the answer is a day in [min bloom, max bloom]. check(day) sweeps left to right, extending a run of adjacent bloomed flowers and cutting a bouquet whenever the run hits k. More days ⇒ more bloomed ⇒ never fewer bouquets, so search the earliest feasible day.
// Binary search the ANSWER (a day) in [min bloom, max bloom]. Later // days only add bloomed flowers, so "can make m bouquets" is monotone. // check() counts runs of k ADJACENT bloomed flowers. int minDays(vector<int>& bloom, int m, int k) { if ((long)m * k > (long)bloom.size()) return -1; // impossible int lo = *min_element(bloom.begin(), bloom.end()); int hi = *max_element(bloom.begin(), bloom.end()); while (lo <= hi) { int mid = lo + (hi - lo) / 2; int made = 0, run = 0; for (int b : bloom) { run = (b <= mid) ? run + 1 : 0; // bloomed extends run if (run == k) { made++; run = 0; } // cut a bouquet } if (made >= m) hi = mid - 1; // enough: earlier day? else lo = mid + 1; // too few: wait longer } return lo; }
// Binary search the ANSWER (a day) in [min bloom, max bloom]. Later // days only add bloomed flowers, so "can make m bouquets" is monotone. // check() counts runs of k ADJACENT bloomed flowers. public int minDays(int[] bloom, int m, int k) { if ((long) m * k > bloom.length) return -1; // impossible int lo = Integer.MAX_VALUE, hi = 0; for (int b : bloom) { lo = Math.min(lo, b); hi = Math.max(hi, b); } while (lo <= hi) { int mid = lo + (hi - lo) / 2; int made = 0, run = 0; for (int b : bloom) { if (b <= mid) { if (++run == k) { made++; run = 0; } } else run = 0; // gap breaks the run } if (made >= m) hi = mid - 1; // enough: try earlier else lo = mid + 1; } return lo; }
# Binary search the ANSWER (a day). More time -> more bloomed -> monotone. # check() counts runs of k ADJACENT bloomed flowers. def min_days(bloom, m, k): if m * k > len(bloom): return -1 # not enough flowers, ever lo, hi = min(bloom), max(bloom) while lo <= hi: mid = lo + (hi - lo) // 2 made = run = 0 for b in bloom: run = run + 1 if b <= mid else 0 if run == k: made += 1; run = 0 if made >= m: hi = mid - 1 # enough: earlier day? else: lo = mid + 1 # too few: wait longer return lo
Skipping the m·k > n guard. When there are not enough flowers to form m bouquets, no day is feasible, and an unguarded search quietly returns hi (the last day) as though it worked. The other slip is counting bloomed flowers ignoring adjacency — a bouquet needs k consecutive bloomed flowers, so the run must reset whenever an unbloomed one breaks it.
The walkthrough for #03 Minimum Days to Make m Bouquets. Watch it, then go straight back and write it yourself.
A divisor problem that is Koko in disguise. The answer is a divisor in [1, max(a)]; check(d) computes Σ ⌈a[i] / d⌉ and asks whether it is ≤ threshold. A larger divisor can only shrink each term, so the sum falls monotonically as d grows — feasibility is F…F T…T and you binary-search the smallest divisor that keeps the sum under the threshold. Structurally identical to unit 2; only the check() body differs, which is exactly the transfer worth internalising.
HOW DO YOU TUNE THE SMALLEST DIVISOR THAT KEEPS A CEIL-SUM UNDER A LIMIT?
As the divisor d increases, what does the sum Σ⌈a[i]/d⌉ do, and which boundary are you after?
The sum weakly decreases, so you want the first passing divisor. Each ⌈a[i]/d⌉ is non-increasing in d, so their sum only falls as the divisor grows; “sum ≤ threshold” is therefore false for small divisors and true from some point on. You want the smallest such divisor — the left boundary of the true region — so on a pass you store it and search left. Same min-feasible move as Koko.
a = [1, 2, 5, 9], threshold = 6. Is divisor 4 feasible, and is it the answer?
Divisor 4 fails with sum 7; 5 is the answer. At d=4 the terms are 1,1,2,3 summing to 7, over the threshold — so the search goes right. At d=5 they are 1,1,1,2 = 5 ≤ 6, feasible, and d=4 having failed makes 5 the smallest that passes. The MECHANISM strip shows the red region (divisors 1-4) and green region (5-9) meeting at 5.
Koko, Smallest Divisor, and Minimum Days share the same eight-line loop. What, concretely, is the only part that changes between them?
Only check() changes. The range endpoints, the while (lo ≤ hi) loop, the midpoint, the store-and-go-left move, and the return lo are shared verbatim; what differs is the one function that turns a candidate into a yes/no — sum of hours, sum of ceils, or count of bouquets. This is the deck's central claim made concrete: learn the skeleton once, and each new problem is a single function you already know how to write.
The answer is a divisor in [1, max(a)]. check(d) sums ⌈a[i] / d⌉; a larger d can only shrink that sum, so feasibility (sum ≤ threshold) is monotone. Binary search the smallest divisor that stays under the threshold. Structurally identical to Koko — only the check() body changes, which is exactly the lesson.
“Smallest divisor / factor such that a sum of ceilings stays under a threshold.” Structurally the same tell as Koko: a value to test, a monotone sum, a minimisation. If you can already write Koko, you can write this by changing one function.
The divisor lives in [1, max(a)]. check(d) = Σ ⌈a[i] / d⌉; a bigger divisor only shrinks the sum, so sum ≤ threshold is monotone. Binary-search the smallest divisor that passes — store and go left on a feasible mid.
// Koko, renamed. Binary search the ANSWER (a divisor) in [1, max(a)]; // a bigger divisor shrinks the ceil-sum, so feasibility is monotone and // we take the smallest divisor whose sum stays <= threshold. int smallestDivisor(vector<int>& a, int threshold) { int lo = 1, hi = *max_element(a.begin(), a.end()); while (lo <= hi) { int mid = lo + (hi - lo) / 2; long sum = 0; for (int x : a) sum += (x + mid - 1) / mid; // ceil(x/mid) if (sum <= threshold) hi = mid - 1; // small enough: shrink d else lo = mid + 1; // sum too big: grow d } return lo; }
// Koko, renamed. Binary search the ANSWER (a divisor) in [1, max(a)]; // a bigger divisor shrinks the ceil-sum, so feasibility is monotone and // we take the smallest divisor whose sum stays <= threshold. public int smallestDivisor(int[] a, int threshold) { int lo = 1, hi = 0; for (int x : a) hi = Math.max(hi, x); while (lo <= hi) { int mid = lo + (hi - lo) / 2; long sum = 0; for (int x : a) sum += (x + mid - 1) / mid; // ceil(x/mid) if (sum <= threshold) hi = mid - 1; // small enough: try a smaller d else lo = mid + 1; } return lo; }
# Koko, renamed. Bigger divisor -> smaller ceil-sum -> monotone. def smallest_divisor(a, threshold): lo, hi = 1, max(a) while lo <= hi: mid = lo + (hi - lo) // 2 s = sum((x + mid - 1) // mid for x in a) # ceil(x/mid) if s <= threshold: hi = mid - 1 # small enough: shrink d else: lo = mid + 1 # sum too big: grow d return lo
Treating it as a new problem. The real risk here is not a bug but missing the reuse — this is Koko with divisor↔speed and sum↔hours, and re-deriving it from scratch wastes the pattern. Mechanically, the same two slips apply: accumulate the ceil-sum in a long, and go left (smaller divisor) on a feasible mid.
The walkthrough for #04 Smallest Divisor Given a Threshold. Watch it, then go straight back and write it yourself.
The first true min-max: minimise the largest load. The answer is a ship capacity in [max weight, total weight] — below the max, one package will not fit; at the total, one day suffices. check(cap) greedily fills the current day until the next package would overflow, then starts a new day, and counts the days used. More capacity never needs more days, so feasibility is monotone and you binary-search the smallest capacity whose day-count stays within D. The greedy check is the whole trick — and it reappears unchanged in unit 7.
HOW DO YOU MINIMISE THE LARGEST LOAD SO EVERYTHING SHIPS WITHIN D DAYS?
Why must the search start at lo = max(weight) rather than lo = 1?
No ship smaller than the heaviest package can ever ship it. The capacity must at least equal max(weight), so the feasible region begins there; anything below is infeasible by definition. Setting lo = 1 does not usually break the search (those values just fail) but it wastes iterations and, in min-max variants that count differently, can let a wrong boundary slip through. Getting the range endpoints right is the most common answer-space slip — here [max, sum] is the exact feasible span.
weights = [1,2,3,4,5,6,7,8,9,10], D = 5. Does capacity 15 ship in time?
Capacity 15 ships in exactly 5 days — the answer. Greedily: day 1 takes 1+2+3+4+5=15, then 6+7=13, then 8, 9, 10 — five days, within D. Capacity 14 splits into six days (1+2+3+4=10 then 5+6=11, …), so it fails; 15 is the smallest that fits. The search brackets it from [10, 55], and the strip shows the feasible (green) region shrinking down to 15.
How is Split Array Largest Sum (unit 7) related to this problem?
They are the same problem. Shipping packages into days under a capacity cap is splitting the array into contiguous groups under a sum cap: a “day” is a “subarray”, the capacity is the “largest allowed sum”, and the greedy pass that counts days counts pieces. Painter's Partition and Book Allocation are the same again. This is why the deck teaches the greedy min-max once, in this unit, and treats unit 7 as its hard apex rather than a new idea.
A min-of-max problem. The answer (a ship capacity) lies in [max weight, total weight]: below the max, one package won't fit; above the total, one day suffices. check(cap) greedily fills days and counts them; more capacity never needs more days. Binary search the smallest capacity whose day-count stays within D. Book Allocation and Painter's Partition are this exact shape.
“Split / pack / partition into k groups and minimise the largest group” — a min-max. Capacity to Ship is the friendly face of the pattern: guess the max load, greedily count the days, minimise. Split Array, Painter's Partition and Book Allocation are the same shape.
The capacity lives in [max weight, total]. check(cap) greedily fills the day until the next package overflows, then opens a new day, and counts days used; more capacity never needs more days. Binary-search the smallest capacity with days ≤ D.
// Min-MAX: binary search the ANSWER (a capacity) in [max weight, sum]. // check(cap) greedily counts the days needed; more capacity never needs // more days, so we take the smallest capacity that fits within D days. int shipWithinDays(vector<int>& w, int D) { int lo = *max_element(w.begin(), w.end()); int hi = accumulate(w.begin(), w.end(), 0); while (lo <= hi) { int mid = lo + (hi - lo) / 2; int days = 1, load = 0; for (int x : w) { if (load + x > mid) { days++; load = 0; } // start a new day load += x; } if (days <= D) hi = mid - 1; // fits: smaller ship? else lo = mid + 1; // too many days: bigger ship } return lo; }
// Min-MAX: binary search the ANSWER (a capacity) in [max weight, sum]. // check(cap) greedily counts the days needed; more capacity never needs // more days, so we take the smallest capacity that fits within D days. public int shipWithinDays(int[] w, int D) { int lo = 0, hi = 0; for (int x : w) { lo = Math.max(lo, x); hi += x; } while (lo <= hi) { int mid = lo + (hi - lo) / 2; int days = 1, load = 0; for (int x : w) { if (load + x > mid) { days++; load = 0; } // start a new day load += x; } if (days <= D) hi = mid - 1; // fits: try a smaller ship else lo = mid + 1; } return lo; }
# Min-MAX: binary search the ANSWER (a capacity) in [max weight, sum]. def ship_within_days(w, D): lo, hi = max(w), sum(w) while lo <= hi: mid = lo + (hi - lo) // 2 days, load = 1, 0 for x in w: if load + x > mid: days += 1; load = 0 # start a new day load += x if days <= D: hi = mid - 1 # fits: smaller ship? else: lo = mid + 1 # too many days: bigger ship return lo
Starting lo at 1 instead of max(weight). A capacity below the heaviest package can never load it, so the feasible region begins at max(weight); the correct range is [max, sum]. Getting the endpoints wrong is the signature min-max mistake — the greedy check and the loop are the easy part.
The walkthrough for #05 Capacity to Ship Packages in D Days. Watch it, then go straight back and write it yourself.
Not every answer-space problem searches a value range — sometimes the monotone quantity is a count along the index. In a strictly increasing array of positives, the number of positive integers missing before a[i] is exactly a[i] − (i + 1), and it only grows with i. So binary-search the first index where that count reaches k — a lower_bound in disguise — and the answer is k + index. O(log n), no linear walk.
HOW DO YOU FIND THE k-th MISSING POSITIVE IN O(log n), NOT O(n)?
Why is a[i] − (i + 1) the count of positive integers missing before a[i]?
It measures how far a[i] has drifted from where it would sit with no gaps. A gapless array of positives is 1, 2, 3, …, so a[i] would be i + 1. Every missing number before it pushes a[i] one higher, so a[i] − (i + 1) counts those misses precisely. Because the array strictly increases, this count is non-decreasing in i — the monotonicity that lets you binary-search it, even though there is no obvious “value range” in sight.
a = [2, 3, 4, 7, 11], k = 5. The search lands with lo = 4 (the first index whose missing-count ≥ 5). What is the answer?
k + lo = 9. The missing counts are [1, 1, 1, 3, 6]; the first index reaching k = 5 is index 4 (count 6), so lo settles at 4 and the answer is 5 + 4 = 9. Checking directly, the missing positives are 1, 5, 6, 8, 9, … and the 5th is indeed 9. The k + lo formula drops out because up to the wall you have accounted for lo present numbers, so the k-th gap sits at k + lo.
What makes this a “binary search on the answer” and not just an array search from deck 1?
You search a derived quantity, and the answer is a number not in the array. Deck 1 searched for a target that lived in the array; here the 9 you return never appears in a. What you binary-search is the function missing(i), using its monotonicity exactly as answer-space problems use a feasibility check. It is the bridge between the two decks: mechanically a lower_bound, but conceptually you are searching for an answer defined by a monotone count — the count-boundary pattern.
Not every answer problem searches a value range: here the monotone quantity is how many positive integers are missing before a[i], which is a[i] − (i+1) and only grows with i. Binary search the first index where that count reaches k — a lower_bound in disguise — then the answer is k + index. O(log n), no linear scan.
“The k-th missing positive”, or any answer defined by a count crossing a target along a sorted array. The monotone quantity is a count, not a value — a lower_bound over a derived key. The give-away is an O(log n) requirement on a strictly increasing array.
In a strictly increasing positive array, the count of positives missing before a[i] is a[i] − (i + 1), which only rises. Binary-search the first index where that count reaches k; everything up to the wall contributes lo present numbers, so the k-th missing is k + lo.
// Answer-space in disguise: the monotone quantity is the missing COUNT // a[i] - (i+1), searched along the index. Find the first index whose // count reaches k (a lower_bound); the answer is k + that index. int findKthPositive(vector<int>& a, int k) { int lo = 0, hi = a.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int missing = a[mid] - (mid + 1); // positives missing before a[mid] if (missing >= k) hi = mid - 1; // enough: look left else lo = mid + 1; // too few: look right } return k + lo; // k plus the index just past the wall }
// Answer-space in disguise: the monotone quantity is the missing COUNT // a[i] - (i+1), searched along the index. Find the first index whose // count reaches k (a lower_bound); the answer is k + that index. public int findKthPositive(int[] a, int k) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int missing = a[mid] - (mid + 1); // positives missing before a[mid] if (missing >= k) hi = mid - 1; // enough: look left else lo = mid + 1; } return k + lo; // lo is the first index reaching k }
# The monotone quantity is the missing COUNT a[i]-(i+1) along the index. # Find the first index whose count reaches k; answer is k + that index. def find_kth_positive(a, k): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 missing = a[mid] - (mid + 1) # positives missing before a[mid] if missing >= k: hi = mid - 1 # enough: look left else: lo = mid + 1 # too few: look right return k + lo
Reaching for the O(n) walk when O(log n) is asked. Counting missing numbers one by one is correct but ignores the structure; the whole point is that a[i] − (i + 1) is monotone, so it is a lower_bound. The boundary detail: after the loop, lo is the first index with enough missing, and the answer is k + lo — not a[lo], which need not exist.
The walkthrough for #06 Kth Missing Positive Number. Watch it, then go straight back and write it yourself.
The hard apex of the min-max family — and, structurally, unit 5 again. Split nums into k contiguous subarrays, minimising the largest subarray sum. The candidate is that largest sum, in [max element, total]; check(cap) greedily starts a new piece whenever the running sum would exceed cap, and counts the pieces. Fewer pieces are always achievable with a larger cap, so it is monotone, and you binary-search the smallest cap needing ≤ k pieces. This is byte-for-byte the Ship Capacity code — recognising that is the point.
HOW DO YOU MINIMISE THE LARGEST PIECE-SUM WHEN SPLITTING INTO k SUBARRAYS?
Why does a greedy left-to-right pass correctly count the minimum pieces for a given cap?
Greedy is optimal for the piece-count. Cutting a new piece only when forced (the next element would exceed cap) keeps every piece as full as possible, and you can prove no strategy uses fewer pieces for the same cap — an exchange argument slides any earlier cut rightward without increasing the count. So check(cap) = “greedy pieces ≤ k” is a sound, monotone feasibility test. This is the same greedy that counts Ship's days; the optimality is what makes the whole min-max family binary-searchable.
nums = [7,2,5,10,8], k = 2. Is a largest-sum cap of 18 feasible, and is it minimal?
Cap 18 splits into exactly two pieces and 17 does not. Greedy with cap 18: 7+2+5 = 14 (adding 10 would hit 24), then 10+8 = 18 — two pieces, feasible. Cap 17: 7+2+5=14, then 10 (8 would overflow), then 8 — three pieces, so 17 fails. Thus 18 is the smallest achievable largest-sum. The search runs over [10, 32]; note the answer 18 is itself one of the subarray sums, as a min-max answer always is.
Aggressive Cows maximises the minimum gap between cows. How does its check differ from Split Array's — and why is the search direction flipped?
Same skeleton, mirrored direction. Aggressive Cows also has a range (possible gaps), a greedy check (place a cow, then the next one at least gap further, count how many fit), and monotonicity — but here a larger gap is harder to satisfy, so feasibility is T…T F…F and you want the largest passing gap. On a feasible mid you store it and go right. Recognising min-feasible vs max-feasible, and flipping the one line accordingly, is the last degree of freedom in the whole pattern.
Split the array into k contiguous pieces, minimising the largest piece-sum. The candidate is that largest sum, in [max element, total]; check(cap) greedily cuts a new piece whenever the running sum would exceed cap and counts the pieces. Fewer pieces are always achievable with a bigger cap — monotone. This is byte-for-byte the Ship Capacity code, which is the point: recognise the shape and the hard problem is already solved.
“Split an array into k contiguous parts, minimise the largest part-sum” (a.k.a. Painter's Partition, Book Allocation). The hardest-sounding member of the min-max family — and, once you see it, the same code as Ship Capacity with different nouns.
The candidate largest-sum lives in [max element, total]. check(cap) greedily starts a new subarray whenever the running sum would exceed cap, counting pieces; fewer pieces need a larger cap, so it is monotone. Binary-search the smallest cap needing ≤ k pieces.
// Byte-for-byte the Ship Capacity code: 'days' -> 'pieces', 'capacity' // -> 'largest allowed sum'. Binary search the ANSWER in [max, sum]; a // bigger cap never needs more pieces, so take the smallest cap with <= k. int splitArray(vector<int>& nums, int k) { int lo = *max_element(nums.begin(), nums.end()); int hi = accumulate(nums.begin(), nums.end(), 0); while (lo <= hi) { int mid = lo + (hi - lo) / 2; int parts = 1, sum = 0; for (int x : nums) { if (sum + x > mid) { parts++; sum = 0; } // cut a new piece sum += x; } if (parts <= k) hi = mid - 1; // few enough: lower the cap else lo = mid + 1; // too many: raise the cap } return lo; }
// Byte-for-byte the Ship Capacity code: 'days' -> 'pieces', 'capacity' // -> 'largest allowed sum'. Binary search the ANSWER in [max, sum]; a // bigger cap never needs more pieces, so take the smallest cap with <= k. public int splitArray(int[] nums, int k) { int lo = 0, hi = 0; for (int x : nums) { lo = Math.max(lo, x); hi += x; } while (lo <= hi) { int mid = lo + (hi - lo) / 2; int parts = 1, sum = 0; for (int x : nums) { if (sum + x > mid) { parts++; sum = 0; } // start a new piece sum += x; } if (parts <= k) hi = mid - 1; // fits: try a tighter cap else lo = mid + 1; } return lo; }
# The Ship Capacity code again: days -> pieces, capacity -> max sum. def split_array(nums, k): lo, hi = max(nums), sum(nums) while lo <= hi: mid = lo + (hi - lo) // 2 parts, s = 1, 0 for x in nums: if s + x > mid: parts += 1; s = 0 # cut a new piece s += x if parts <= k: hi = mid - 1 # few enough: lower the cap else: lo = mid + 1 # too many: raise the cap return lo
Reaching for DP because the problem 'sounds hard'. The O(n²k) interval DP is correct but heavier and slower than recognising the min-max shape — the binary search on the answer is O(n log sum) and reuses code you already have. The mechanical slip is the same as Ship: lo must start at max(nums), not 1, or a single oversized element breaks feasibility.
The walkthrough for #07 Split Array Largest Sum. Watch it, then go straight back and write it yourself.
The apex of the deck. A median splits the combined arrays into a left half and a right half of equal size — so instead of merging in O(m+n), binary-search where to cut the smaller array. Fixing a cut ca in a forces the cut in b to cb = half − ca, so the two left parts always hold exactly half the elements. The cut is valid when every left element ≤ every right element — checked with only the four boundary values: L1 ≤ R2 and L2 ≤ R1. Empty sides use ±∞ sentinels.
HOW DO YOU FIND THE MEDIAN OF TWO SORTED ARRAYS IN O(log min(m, n))?
Once you fix the cut position ca in array a, why is the cut in b completely determined?
The equal-halves requirement forces cb. The median needs the left side to contain exactly ⌈(m+n)/2⌉ elements; if ca of them come from a, the remaining half − ca must come from b. So there is only one knob to turn, ca, and you binary-search it — the whole reason a two-array problem collapses to a single O(log) search. This is why merging is unnecessary: you are searching cut positions, not values.
a = [1,3,8], b = [7,9,10,11], half = 4. At ca = 2 (so cb = 2): L1=3, R1=8, L2=9, R2=10. Valid?
Invalid because L2 = 9 > R1 = 8. A left element of b (9) exceeds a right element of a (8), so the left half is not entirely ≤ the right half — the cut took too few from a, and you move it right to ca = 3. There L1=8, R1=+∞, L2=7, R2=9 satisfy both 8 ≤ 9 and 7 ≤ +∞; the total is odd, so the median is max(L1, L2) = 8. The cut surface shows the two failing/holding inequalities light red and green.
This median search runs on the larger array and indexes out of bounds. What is the one-line fix?
int m = a.size(), n = b.size(); // (missing) search a directly int half = (m + n + 1) / 2; int cb = half - ca; // can exceed n!
Search the smaller array. If a is the larger one, ca can be big enough that cb = half − ca goes negative or, when ca is small, exceeds n — either way an out-of-bounds cut. Guaranteeing m ≤ n with a one-line swap keeps cb ∈ [0, n] for every valid ca ∈ [0, m], and as a bonus makes the complexity O(log min(m, n)). It is the single most common way this famously fiddly problem breaks.
The apex. A median splits the combined arrays into a left half and a right half of equal size, so instead of merging (O(m+n)) you binary search where to cut the smaller array; the other cut is forced so the two left parts hold exactly half the elements. A cut is valid when every left element ≤ every right element — checked with just the four boundary values: L1 ≤ R2 and L2 ≤ R1. O(log min(m, n)).
“Median (or k-th element) of two sorted arrays in O(log) time.” The log requirement forbids merging; the only thing left to search is where to cut. The hardest binary search in the syllabus, and the purest example of searching a position rather than a value.
Cut the smaller array at ca; the other cut is forced to cb = half − ca so the two left parts hold half the elements. The four boundary values L1, R1, L2, R2 decide validity: the cut is right when L1 ≤ R2 and L2 ≤ R1. If L1 > R2 you took too many from a (move left); if L2 > R1, too few (move right).
// Don't merge. Binary search the CUT in the SMALLER array; the other // cut is forced so both left halves hold exactly half the elements. A // cut is valid when every left value <= every right value: L1<=R2, L2<=R1. double findMedianSortedArrays(vector<int>& a, vector<int>& b) { if (a.size() > b.size()) return findMedianSortedArrays(b, a); int m = a.size(), n = b.size(), half = (m + n + 1) / 2; int lo = 0, hi = m; while (lo <= hi) { int ca = (lo + hi) / 2, cb = half - ca; int L1 = ca ? a[ca-1] : INT_MIN, R1 = ca < m ? a[ca] : INT_MAX; int L2 = cb ? b[cb-1] : INT_MIN, R2 = cb < n ? b[cb] : INT_MAX; if (L1 <= R2 && L2 <= R1) { // valid partition if ((m + n) & 1) return max(L1, L2); return (max(L1, L2) + min(R1, R2)) / 2.0; } else if (L1 > R2) hi = ca - 1; // too many from a: cut left else lo = ca + 1; // too few from a: cut right } return 0.0; }
// Don't merge. Binary search the CUT in the SMALLER array; the other // cut is forced so both left halves hold exactly half the elements. A // cut is valid when every left value <= every right value: L1<=R2, L2<=R1. public double findMedianSortedArrays(int[] a, int[] b) { if (a.length > b.length) return findMedianSortedArrays(b, a); int m = a.length, n = b.length, half = (m + n + 1) / 2; int lo = 0, hi = m; while (lo <= hi) { int ca = (lo + hi) / 2, cb = half - ca; int L1 = (ca == 0) ? Integer.MIN_VALUE : a[ca - 1]; int R1 = (ca == m) ? Integer.MAX_VALUE : a[ca]; int L2 = (cb == 0) ? Integer.MIN_VALUE : b[cb - 1]; int R2 = (cb == n) ? Integer.MAX_VALUE : b[cb]; if (L1 <= R2 && L2 <= R1) { // valid cut if (((m + n) & 1) == 1) return Math.max(L1, L2); return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0; } if (L1 > R2) hi = ca - 1; // took too many from a else lo = ca + 1; // took too few } return 0.0; }
# Don't merge. Binary search the CUT in the SMALLER array; the other # cut is forced. Valid when L1 <= R2 and L2 <= R1. def find_median_sorted_arrays(a, b): if len(a) > len(b): a, b = b, a m, n, half = len(a), len(b), (len(a) + len(b) + 1) // 2 lo, hi = 0, m INF = float('inf') while lo <= hi: ca = (lo + hi) // 2; cb = half - ca L1 = a[ca-1] if ca else -INF; R1 = a[ca] if ca < m else INF L2 = b[cb-1] if cb else -INF; R2 = b[cb] if cb < n else INF if L1 <= R2 and L2 <= R1: # valid partition if (m + n) & 1: return max(L1, L2) return (max(L1, L2) + min(R1, R2)) / 2.0 elif L1 > R2: hi = ca - 1 # too many from a: cut left else: lo = ca + 1 # too few from a: cut right return 0.0
Searching the larger array, or dropping the ±∞ sentinels. If a is not the smaller array, cb = half − ca can fall outside [0, n] and index out of bounds — the one-line swap guarantees it stays valid and pins the complexity to O(log min(m,n)). And an empty left/right side must read as ∓∞, or the L ≤ R checks reject a genuinely valid edge cut.
The walkthrough for #08 Median of Two Sorted Arrays. Watch it, then go straight back and write it yourself.
“Place k cows in stalls at given positions to maximise the minimum gap” (Aggressive Cows), and “divide books among k students minimising the max pages” (Book Allocation). How many new ideas are here?
No new ideas — same shape, twice. Aggressive Cows searches the gap: check(g) greedily places cows at least g apart and asks if k fit — bigger gaps are harder, so it is max-feasible (largest g that still fits k cows). Book Allocation is byte-for-byte Split Array Largest Sum: check(cap) counts students and you minimise the cap. Recognising that four differently-worded problems are one check() apart is exactly the transfer this deck trains — the hard part is never the binary search, it is seeing the shape.
Before writing an answer-space binary search, what three things must you pin down?
Range, monotone check, and boundary direction. Every problem in this deck is those three choices: what range the answer lives in (get the endpoints right — Ship's lo = max is a classic slip), what yes/no test decides feasibility (and a proof that it is monotone), and which side of the F…T boundary is the answer (smallest passing, or largest holding). Nail those three and the loop is the same eight lines you already know. Skip the monotonicity proof and you will binary-search a predicate that lies to you.
Answer-space search is short, and every one of its bugs still compiles and returns a number. A wrong bound, a non-monotone check, or the wrong move on a pass gives a plausible, wrong answer.
The range must actually contain the answer. Ship and Split start at lo = max(element) (a single item bigger than the cap makes it infeasible forever) and hi = sum. Start lo = 1 and you can return a capacity that cannot hold the biggest package.
The whole method assumes check is F…F T…T. If it is not — e.g. you check “exactly k groups” instead of “at most k” — binary search silently converges to a non-answer. Always phrase the check as a monotone ≤ / ≥.
On a passing mid, do you go left or right? Smallest-feasible goes left (hi = mid − 1); largest-that-holds (like Sqrt) goes right. Getting it backwards returns the far end of the feasible region — a plausible, wrong number.
With hi up to 10⁹ or 10¹⁸, (lo + hi) overflows — use lo + (hi − lo)/2. The feasibility sum overflows too: accumulate hours, loads and sums in a 64-bit long, not int.
Bouquets needs m·k ≤ n flowers or the answer is −1; without the guard the search runs to hi and returns a day that can never yield enough. Check feasibility of the whole range before trusting the boundary.
The partition search must run on the smaller array so cb = half − ca stays in range; forgetting the if (m > n) swap gives a negative or oversized cut. And the empty-side sentinels must be ±∞, not 0.
Eight searches, one reframe. The right-hand column is the recognition — the check() you run at each guess — which is the part that is actually hard.
Once “binary search the answer” is automatic, a whole tier of “minimise the maximum” and “smallest value such that” problems stops looking hard and starts looking like one function you already know how to write.
Lectures are Striver's A2Z DSA course. Problem links are LeetCode. 8 answer-space units from the 29-lecture playlist; the array searches are deck 1.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.