ONE COLLAPSE, EVERY ALGORITHM
YOUR CALL
Every one of these is the same move: keep a live interval [lo, hi] and throw away half of it each step, until one element remains. What changes from problem to problem is only the question you ask at mid - and once you see that, eleven problems become one.
This is not a list of problems. It is 10 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
11 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 is the same collapse of an interval. What the cards below name is the question you ask at mid — and hearing which question a statement is asking for is the entire skill.
sorted is the invitation; one comparison discards half
PLAIN BINARY SEARCH — a[mid] vs targetO(log n) time · O(1) spaceyou need a boundary, not just any match
lower_bound / upper_bound — store and keep goingO(log n) time · O(1) spacenot globally sorted, but one half always is
IDENTIFY THE SORTED HALF, then discard the otherO(log n) · O(n) if duplicatesthe pairing's parity breaks exactly at the answer
BINARY SEARCH ON PAIR PARITYO(log n) time · O(1) spacea[mid] vs a[mid+1] gives a direction even without order
FOLLOW THE SLOPE UPHILLO(log n) time · O(1) space2D sortedness is 1D sortedness in disguise, or a staircase
FLATTEN TO 1D, or walk from a cornerO(log mn) or O(m+n)Binary search is what you reach for when the bound is enormous and the structure is sorted. Type a value for n and the row that survives lights up.
THE GOLD-EDGED ROWS ARE WHERE THIS DECK LIVES · LINEAR DIES LONG BEFORE log n DOES · DECK 2 PUSHES THE RANGE TO 10¹⁸
All 10 units, one collapse. Seven search a 1D array; three carry the idea into a matrix. The answer-space reframe — sqrt, koko, split array, median — is deck 2.
Why write mid = lo + (hi − lo) / 2 instead of the obvious mid = (lo + hi) / 2?
Overflow. When lo and hi are both near INT_MAX — which happens in binary-search-on-answers with large bounds — lo + hi wraps past 2³¹ to a negative number, and mid becomes a garbage index that crashes or reads out of bounds. lo + (hi − lo) / 2 never forms the oversized sum yet computes the same midpoint. It is the most famous bug in binary search — it lived in the JDK's own library for nearly a decade — and writing it the safe way costs nothing.
Given n ≤ 10⁹ and a sorted array, what target complexity should you aim for before writing anything?
O(log n). At 10⁹ even a single linear pass is on the edge, and the word sorted is the tell: it is the precondition binary search needs. Reading “sorted” plus a large bound and reaching for log n before you have thought about the specific problem is exactly the constraint-first habit this deck drills — the target complexity is often decidable from the input size alone. The underlying budget is the same one Sorting (step 02) and Arrays 1 (step 03) derive: about 10⁸ operations a second. Only the bound changes.
This binary search loops forever on some inputs. Which line causes it?
while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < t) lo = mid + 1; else hi = mid; // target could be at mid }
An infinite loop from an interval that stops shrinking. Once hi = lo + 1, mid = lo + (1)/2 = lo — mid is pinned to lo. Pairing hi = mid with lo = mid then moves neither bound: whichever branch runs, the interval is unchanged and the next iteration computes the same mid forever. The rule: whichever side keeps mid, the other must step past it — one of the two updates is always mid ± 1. Writing lo = mid and hi = mid in the same loop is how binary searches hang.
This is the whole topic in one move, and everything else in both decks is a variation on it. Keep a live interval [lo, hi] that is guaranteed to contain the answer if it exists. Look at the middle; because the array is sorted, one comparison tells you which half the answer cannot be in, and you throw that half away. Repeat, and the interval collapses from n elements to one in about log₂ n steps.
HOW DO YOU FIND A VALUE IN A SORTED ARRAY WITHOUT LOOKING AT MOST OF IT?
What is the loop invariant that makes binary search correct — the property true before every iteration?
The answer, if it exists, is inside [lo, hi]. That single sentence is what every step must preserve, and it is why discarding a half is safe: you only ever throw away elements you have proven cannot be the answer. Sortedness is what lets one comparison do that proving, but the invariant is the thing you reason about. Every binary-search bug is ultimately a step that violates it — discarding a half that could still contain the answer, or failing to shrink and looping forever. State the invariant and the code writes itself.
On [3, 8, 12, 19, 24, 31, 42, 55] searching for 42, what is mid at the very first step, and which half is discarded?
mid = (0+7)/2 = 3, so a[mid] = 19. Since 19 < 42, the target must be to the right — everything at index 3 or below is too small — so lo jumps to 4 and the left half vanishes. The search then finds 42 at index 6 two steps later. Watch the MECHANISM slide strike out the discarded half each step; in PREDICT mode it asks you which half survives at every comparison.
This returns -1 for a target that IS in the array. Which line is the bug?
while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return mid; if (a[mid] < t) hi = mid - 1; else lo = mid + 1; }
The branches are backwards. When a[mid] < t, the middle value is too small, so the answer lies to the right — you must raise lo to mid + 1, not lower hi. As written it discards the half that actually contains the target and searches the wrong side, returning -1. It even works by luck when the target happens to sit at the first mid. Tie the direction to the invariant every time: too small ⇒ go right, too big ⇒ go left, and the branches cannot be swapped.
The one invariant behind the whole topic: the answer, if it exists, is always inside [lo, hi]. Look at the middle, and because the array is sorted, one comparison rules out an entire half. Watch the eliminated side strike through — that collapse from n to 1 in log n steps is the entire idea. Note lo + (hi−lo)/2, not (lo+hi)/2: the latter can overflow on large indices.
The two words that matter are sorted and O(log n) — the constraint (often n ≤ 10⁵ or far more) rules out a linear scan, and sortedness is the precondition binary search needs. When you see a sorted array and a target to locate, this is the default, not a clever trick to search for.
Maintain [lo, hi] guaranteed to contain the target if present. Look at the middle: if it equals the target you are done; if it is too small the answer is strictly to the right, so raise lo; if too big, lower hi. Each step halves the interval, so it collapses to empty (target absent) or a match in about log₂ n steps.
// The invariant: the target, if present, is always inside [lo, hi]. // One comparison at the middle discards a whole half, because the array // is sorted. mid = lo + (hi-lo)/2 avoids the (lo+hi) overflow. int search(vector<int>& a, int t) { int lo = 0, hi = a.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return mid; if (a[mid] < t) lo = mid + 1; // too small: answer is right else hi = mid - 1; // too big: answer is left } return -1; }
// The invariant: the target, if present, is always inside [lo, hi]. // One comparison at the middle discards a whole half, because the array // is sorted. mid = lo + (hi-lo)/2 avoids the (lo+hi) overflow. public int search(int[] a, int t) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return mid; if (a[mid] < t) lo = mid + 1; // target is right of mid else hi = mid - 1; // target is left of mid } return -1; // interval emptied: absent }
# The invariant: the target, if present, is always inside [lo, hi]. # One comparison at the middle discards a whole half, because the array # is sorted. (Python ints never overflow, but keep the safe midpoint habit.) def search(a, t): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] == t: return mid if a[mid] < t: lo = mid + 1 # too small: answer is right else: hi = mid - 1 # too big: answer is left return -1
Swapping the two branches — moving hi when the middle is too small — searches the wrong half and returns -1 for present targets. Tie the direction to the meaning: too small means go right. The other classic is mid = (lo + hi) / 2, which overflows once indices get large (as they do in deck 2's answer-space searches); write lo + (hi − lo) / 2 from the start so the habit is already there when it matters.
The walkthrough for #01 Binary Search. Watch it, then go straight back and write it yourself.
The single most reusable primitive in the topic. lower_bound finds the first index with a[i] ≥ target; upper_bound the first with a[i] > target. The trick that separates them from plain search is what you do on a candidate: you do not stop — you record the index and keep searching left for an even earlier one. Search Insert Position is literally lower_bound, and counts, ranges and floors all fall out of these two.
HOW DO YOU FIND WHERE A VALUE BELONGS, EVEN WHEN IT IS NOT PRESENT?
What distinguishes lower_bound from a plain binary search that returns on a match?
It refuses to stop early. Plain search returns the moment a[mid] qualifies; lower_bound instead saves mid as the best-so-far and continues into the left half looking for an earlier qualifier. That “store and keep going” is the whole difference, and it is why lower_bound gives you the first index with a[i] ≥ t rather than an arbitrary one. Everything else — insert position, counts, floor and ceil — is a thin wrapper over this one behaviour.
On [1, 3, 3, 5, 8, 8, 8, 11], what does lower_bound(8) return, and what would upper_bound(8) return?
lower_bound(8) = 4 (the first 8, at index 4) and upper_bound(8) = 7 (the first element strictly greater than 8, the 11 at index 7). Their difference, 7 − 4 = 3, is exactly the number of 8s — which is how you count occurrences in O(log n) with no scan. Search Insert for 8 would also return 4, since that is where an 8 belongs. The MECHANISM slide shows the candidate marker sliding left as earlier 8s are found.
You need the floor of a target (largest element ≤ target) in a sorted array. How does it relate to these primitives?
floor sits at upper_bound(target) − 1. upper_bound gives the first element strictly greater than the target, so the element just before it is the largest one that is ≤ target — the floor (guarding for index 0, meaning no floor exists). Ceil is the mirror: it is lower_bound(target) directly. Once you see floor and ceil as ±1 offsets of these two bounds, a whole class of “nearest value” problems becomes two-line wrappers instead of fresh searches.
The primitive behind half of this deck. lower_bound finds the first index with a[i] ≥ target, so on a hit it does not return — it records the candidate and searches further left for an even earlier one. Start the answer at n (“not found”). Search Insert Position is exactly this, and upper_bound is the same with >.
“Return the index where the target is, or would be inserted” in a sorted array. “Would be inserted” is the giveaway that a plain find-or-fail search is not enough — you need the position even when the target is absent, which is precisely lower_bound.
Run lower_bound: the first index i with a[i] ≥ target. On a qualifying mid, store it and search left for an earlier one; otherwise search right. Whatever candidate survives is where the target belongs — if it is present, that is its index; if not, that is where it would slot in to keep the array sorted. Start the answer at n so an all-smaller array inserts at the end.
// Search Insert Position IS lower_bound: the first index with a[i] >= t. // On a qualifying mid, store it and keep looking LEFT for an earlier one. int searchInsert(vector<int>& a, int t) { int lo = 0, hi = a.size() - 1, ans = a.size(); while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= t) { ans = mid; hi = mid - 1; } // store, keep left else lo = mid + 1; } return ans; }
// Search Insert Position IS lower_bound: the first index with a[i] >= t. // On a qualifying mid, store it and keep looking LEFT for an earlier one. public int searchInsert(int[] a, int t) { int lo = 0, hi = a.length - 1, ans = a.length; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= t) { ans = mid; hi = mid - 1; } // store, keep left else lo = mid + 1; } return ans; // insertion point == the count below t }
# Search Insert Position IS lower_bound: the first index with a[i] >= t. # On a qualifying mid, store it and keep looking LEFT for an earlier one. def search_insert(a, t): lo, hi, ans = 0, len(a) - 1, len(a) while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] >= t: ans = mid; hi = mid - 1 # store, keep left else: lo = mid + 1 return ans
Returning on the first a[mid] == target gives an occurrence, not the insert position, and — worse — not even the first occurrence when there are duplicates. Always store and keep searching left. The mirror mistake is initialising ans = -1 or n − 1: when every element is smaller than the target the answer is n (append at the end), so that must be the default the search falls back to.
The walkthrough for #02 Search Insert Position. Watch it, then go straight back and write it yourself.
Plain binary search finds an occurrence of a value; this problem wants the first and the last. Both are boundary searches: for the first, on a match you record and keep going left; for the last, you keep going right. Equivalently the first occurrence is lower_bound(t) and the last is lower_bound(t+1) − 1 — so the whole problem is two calls to the primitive you just learned, and the count of occurrences is their difference plus one.
HOW DO YOU FIND THE FULL RANGE OF A REPEATED VALUE IN O(log n)?
To find the LAST occurrence of a value, what do you do when a[mid] equals the target?
Record and go right. Finding the last occurrence is the mirror of finding the first: on a match you still refuse to stop, but now you bias toward the right half, saving mid and setting lo = mid + 1 to hunt for a later match. First-occurrence biases left, last biases right, and both are the “store, keep going” move from lower_bound. Two nearly identical searches bracket the value's range.
On [2, 4, 4, 4, 4, 6, 7, 9] searching for 4, the first-occurrence pass finds index 1. How many 4s are there, using the boundary trick?
Four. The first 4 is at index 1 and the last is at index 4, so the count is last − first + 1 = 4 − 1 + 1 = 4. Equivalently, lower_bound(4) = 1 and lower_bound(5) = 5, and 5 − 1 = 4. Both routes give the same answer with two O(log n) searches and no counting scan — the payoff of treating occurrence-counting as a pair of boundary searches.
This find-first returns index 3 for the first 4 in [2,4,4,4,4,6], when it should return 1. Which line is wrong?
if (a[mid] == t) return mid; else if (a[mid] < t) lo = mid + 1; else hi = mid - 1;
Returning on the first match abandons the boundary search. On [2,4,4,4,4,6] the first mid is index 2 (a 4), and returning it gives 2 — or with different sizes, 3 — never guaranteed to be the leftmost 4. To find the first, replace return mid with “record mid, then hi = mid − 1” so the search continues into the left half. This is the exact mistake the unit's concept warns about: a match is the middle of the search, not the end.
Plain binary search returns any occurrence; this problem needs the first and the last. So on a match you record the index and keep narrowing toward it — left for the first, right for the last. Two lower-bound-style passes, or lower_bound(t) and lower_bound(t+1)−1. Stopping early is the mistake this whole unit exists to prevent.
“Find the first and last position” of a value, or “count occurrences”, in a sorted array, in O(log n). The plural — a range rather than a single index — plus the log bound is the signal for two boundary searches, not one plain search that stops at any match.
Run lower_bound twice. The first occurrence is lower_bound(target): the first index with a[i] ≥ target (verify it actually equals the target, else the value is absent). The last occurrence is lower_bound(target + 1) − 1: one step before where values first exceed the target. The count is their difference plus one. Equivalently, bias one search left on a match and the other right.
// Two boundary searches. First occurrence biases LEFT on a match; // last occurrence biases RIGHT. The value's range is [first, last], and // the count is last - first + 1. vector<int> searchRange(vector<int>& a, int t) { auto bound = [&](int t) { // lower_bound(t) int lo = 0, hi = a.size() - 1, ans = a.size(); while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] >= t) { ans = mid; hi = mid - 1; } else lo = mid + 1; } return ans; }; int first = bound(t); if (first == (int)a.size() || a[first] != t) return {-1, -1}; return {first, bound(t + 1) - 1}; }
// Two boundary searches. First occurrence biases LEFT on a match; // last occurrence biases RIGHT. The value's range is [first, last], and // the count is last - first + 1. public int[] searchRange(int[] a, int t) { int first = bound(a, t, true), last = bound(a, t, false); return new int[]{first, last}; } private int bound(int[] a, int t, boolean leftBias) { int lo = 0, hi = a.length - 1, ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) { ans = mid; // record, then keep going if (leftBias) hi = mid - 1; // an earlier one may exist else lo = mid + 1; // a later one may exist } else if (a[mid] < t) lo = mid + 1; else hi = mid - 1; } return ans; }
# Two boundary searches. First occurrence biases LEFT on a match; # last occurrence biases RIGHT. The value's range is [first, last], and # the count is last - first + 1. def search_range(a, t): def bound(t): # lower_bound(t) lo, hi, ans = 0, len(a) - 1, len(a) while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] >= t: ans = mid; hi = mid - 1 else: lo = mid + 1 return ans first = bound(t) if first == len(a) or a[first] != t: return [-1, -1] return [first, bound(t + 1) - 1]
Finding one occurrence and then scanning outward for the range is O(n) in the worst case — an array that is all the same value degrades the “scan to the edges” step to linear, defeating the point. Both boundaries must be found by binary search. The other trap is forgetting the presence check: lower_bound(target) returns a valid index even when the target is absent (it points at the next-larger element), so you must confirm a[first] == target before trusting the range.
The walkthrough for #03 Find First and Last Position. Watch it, then go straight back and write it yourself.
A sorted array rotated at an unknown pivot is no longer globally sorted — but the saving insight is that at any mid, at least one of the two halves is still perfectly sorted. Compare a[lo] to a[mid] to find which half that is; then check whether the target lies within that sorted half's known range. If it does, search there; if not, the target must be in the other half. Duplicates (Search II) are the one wrinkle: they can make the sorted half impossible to identify.
HOW DO YOU BINARY-SEARCH AN ARRAY THAT IS SORTED BUT ROTATED?
At any mid in a rotated sorted array, how do you tell which half is the sorted one?
a[lo] ≤ a[mid] means the left half is sorted. If the value at the low end is not greater than the value at the middle, then [lo..mid] contains no rotation drop and is in order; otherwise the drop is in the left half, which forces the right half [mid..hi] to be the sorted one. Exactly one half always qualifies, and identifying it is the whole move — once you know the sorted half's range, a single containment check tells you which side to discard.
On [7, 8, 9, 1, 2, 3, 4, 5] searching for 2, the first mid is index 3 (value 1). Which half is sorted, and where does the search go?
The right half is sorted, and the target is in it. a[lo] = 7 > a[mid] = 1, so the left half holds the drop and the right half [1, 2, 3, 4, 5] is the sorted one. The target 2 lies between a[mid] = 1 and a[hi] = 5, so it must be in that sorted right half — lo jumps to mid + 1. Two steps later it lands on 2. In PREDICT mode the MECHANISM slide asks you, at each mid, whether the target lies in the sorted half.
Why does adding duplicates (Search II) break the O(log n) guarantee?
The identification step fails. The whole method rests on comparing a[lo] and a[mid] to find the sorted half — but when a[lo] == a[mid] == a[hi] (e.g. [3, 1, 3, 3, 3]), that comparison is uninformative: the sorted half could be either side. The only safe move is to nibble one element off each end (lo++, hi--) and retry, and in the worst case — an array of all-but-one identical values — that is O(n). Search II is Search I plus this one guard, which the next slide shows as a one-line diff.
A rotated array is not sorted, but at any mid at least one of [lo..mid] and [mid..hi] still is. Compare a[lo] to a[mid] to identify the sorted half, check whether the target falls inside its known range, and discard the half that provably cannot hold it. Everything hard about rotation reduces to that one identification.
“Rotated sorted array” with a target to find, in O(log n). The word rotated is the whole signal: the array is almost sorted, and the log bound insists you exploit that rather than scan. The move is to find the half that is still sorted at each step.
At any mid, compare a[lo] to a[mid] to identify the sorted half. If the left half is sorted and the target lies within [a[lo], a[mid]), search left; otherwise search right. If instead the right half is sorted and the target lies within (a[mid], a[hi]], search right; otherwise left. Each step still discards a full half, so it stays logarithmic.
// One half is always sorted. Identify it via a[lo] vs a[mid], check // whether the target lies in that sorted half's known range, and discard // the half that provably cannot contain it. int search(vector<int>& a, int t) { int lo = 0, hi = a.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return mid; if (a[lo] <= a[mid]) { // LEFT half sorted if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1; } else { // RIGHT half sorted if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; }
// One half is always sorted. Identify it via a[lo] vs a[mid], check // whether the target lies in that sorted half's known range, and discard // the half that provably cannot contain it. public int search(int[] a, int t) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return mid; if (a[lo] <= a[mid]) { // LEFT half is sorted if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1; } else { // RIGHT half is sorted if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1; } } return -1; }
# One half is always sorted. Identify it via a[lo] vs a[mid], check # whether the target lies in that sorted half's known range, and discard # the half that provably cannot contain it. def search(a, t): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] == t: return mid if a[lo] <= a[mid]: # LEFT half sorted if a[lo] <= t < a[mid]: hi = mid - 1 else: lo = mid + 1 else: # RIGHT half sorted if a[mid] < t <= a[hi]: lo = mid + 1 else: hi = mid - 1 return -1
Getting the range-inclusion boundaries wrong. The sorted-half check must use the right open/closed ends: for the sorted left half the target qualifies when a[lo] ≤ t < a[mid] (mid itself was already checked for equality), and for the sorted right half when a[mid] < t ≤ a[hi]. Flip an inclusive bound to exclusive and you occasionally discard the half that holds the target, returning -1 for a present value. Test against a rotation that puts the target adjacent to the pivot — that is where the boundary errors surface.
The walkthrough for #04 Search in Rotated Sorted Array. Watch it, then go straight back and write it yourself.
Identical to Search in Rotated Sorted Array, with one added phrase: “may contain duplicates”. That single change is the whole problem — duplicates can make it impossible to tell which half is sorted, so you need one extra guard, and you must accept that the worst case is no longer O(log n).
Everything from the no-duplicates version, plus one case at the top of the loop: when a[lo] == a[mid] == a[hi], the comparison that identifies the sorted half is useless, so you cannot decide a direction. The only safe move is to shrink both ends by one (lo++, hi--) and retry. This is what drags the worst case to O(n) — an array of nearly all identical values forces the nibbling to happen n times.
bool search(vector<int>& a, int t) { int lo = 0, hi = a.size() - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return true; if (a[lo] == a[mid] && a[mid] == a[hi]) { lo++; hi--; continue; } if (a[lo] <= a[mid]) { // LEFT half sorted if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1; } else { // RIGHT half sorted if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1; } } return false; }
// Duplicates break the "which half is sorted" test: when all three ends // are equal you cannot tell, so shrink both by one. That step is what // costs the O(log n) guarantee and degrades to O(n) in the worst case. public boolean search(int[] a, int t) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (a[mid] == t) return true; if (a[lo] == a[mid] && a[mid] == a[hi]) { lo++; hi--; continue; } if (a[lo] <= a[mid]) { // LEFT half sorted if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1; } else { // RIGHT half sorted if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1; } } return false; }
def search(a, t): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if a[mid] == t: return True if a[lo] == a[mid] == a[hi]: lo += 1; hi -= 1; continue if a[lo] <= a[mid]: # LEFT half sorted if a[lo] <= t < a[mid]: hi = mid - 1 else: lo = mid + 1 else: # RIGHT half sorted if a[mid] < t <= a[hi]: lo = mid + 1 else: hi = mid - 1 return False
Reusing the Rotated I code unchanged gives wrong answers on inputs like [3, 1, 2, 3, 3, 3, 3]: with a[lo] == a[mid] == a[hi] == 3, the a[lo] ≤ a[mid] test claims the left half is sorted and the target gets searched on the wrong side. The one-line guard fixes correctness. The subtler trap is claiming O(log n) in an interview — be honest that duplicates force O(n) worst case, because that awareness is part of what the follow-up problem is testing.
The walkthrough for #05 Search in Rotated Sorted Array II. Watch it, then go straight back and write it yourself.
Finding the minimum of a rotated sorted array is binary search with no target at all — the comparison is between a[mid] and a[hi]. If a[mid] > a[hi] the rotation drop (and therefore the minimum) is strictly to the right; otherwise the right half is already sorted and the minimum is at mid or to its left. The index where the interval settles is not just the minimum — it is also how many times the array was rotated.
HOW DO YOU FIND THE SMALLEST ELEMENT — AND THE ROTATION COUNT — IN O(log n)?
Why compare a[mid] to a[hi] rather than to a[lo] when finding the minimum?
a[hi] disambiguates the unrotated case. Comparing against a[lo] stumbles when the current interval is already sorted (no drop), because then a[mid] ≥ a[lo] is true but tells you nothing about where the minimum is. Comparing against a[hi] is clean: a[mid] > a[hi] is true if and only if the drop lies strictly to the right of mid, and a[mid] ≤ a[hi] means the right half is sorted so the minimum is at mid or left. One comparison, no special cases.
This find-min uses hi = mid - 1 in the else branch. On [4, 5, 6, 7, 0, 1, 2, 3] it can miss the minimum. Why?
if (a[mid] > a[hi]) lo = mid + 1; else hi = mid - 1; // min is here or left
hi = mid − 1 can throw away the minimum itself. The else branch fires when a[mid] ≤ a[hi], which means mid could be the minimum (the right half is sorted and starts at mid). Setting hi = mid − 1 excludes mid from the interval and you lose it. The correct shrink keeps it: hi = mid. This is the deck-wide rule — when mid might be the answer, shrink to mid, not mid ± 1 — and find-min is where it bites hardest.
You need to know how many times the array was rotated, not the minimum value itself. What changes?
Return the index, not the value. A right-rotation by k moves the original first element to position k, and the original minimum (which was at index 0) lands at exactly index k. So the position of the minimum is the rotation count — the same search answers both questions, you just report a different field. This is why the lecture on “how many times rotated” needs no separate unit: it is find-min reading out its index instead of its value.
There is nothing to search for, yet binary search still applies. a[mid] > a[hi] means the rotation point — and the minimum — lies strictly to the right; otherwise the minimum is at mid or left, so hi = mid (never mid−1, because mid itself might be it). The index where it settles is also how many times the array was rotated.
“Find the minimum in a rotated sorted array”, O(log n), no target given. “No target” is the distinctive part: the comparison is not against a value you are looking for but between a[mid] and a[hi], to locate the rotation drop.
The minimum is the single point where the array “drops”. Compare a[mid] with a[hi]: if a[mid] > a[hi], the drop is strictly to the right, so the minimum is there — move lo past mid. Otherwise the right half is sorted with no drop, so the minimum is at mid or to its left — set hi = mid, keeping mid because it might be the answer. When the interval collapses, lo points at the minimum, and that index is the rotation count.
// No target: compare a[mid] to a[hi] to locate the rotation drop. // hi = mid, never mid-1 -- mid itself might be the minimum. int findMin(vector<int>& a) { int lo = 0, hi = a.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > a[hi]) lo = mid + 1; // drop is to the right else hi = mid; // min is mid or left } return a[lo]; // lo is also the rotation count }
// No target: compare a[mid] to a[hi] to locate the rotation drop. // hi = mid, never mid-1 -- mid itself might be the minimum. public int findMin(int[] a) { int lo = 0, hi = a.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > a[hi]) lo = mid + 1; // drop is to the right else hi = mid; // min is mid or left of it } return a[lo]; // lo == hi: the minimum }
# No target: compare a[mid] to a[hi] to locate the rotation drop. # hi = mid, never mid-1 -- mid itself might be the minimum. def find_min(a): lo, hi = 0, len(a) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if a[mid] > a[hi]: lo = mid + 1 # drop is to the right else: hi = mid # min is mid or left return a[lo] # lo is also the rotation count
Writing hi = mid − 1 in the else branch can discard the minimum itself, since that branch fires precisely when mid might be it. The shrink must be hi = mid, paired with a lo < hi loop so it still terminates. The second trap is comparing a[mid] to a[lo] instead of a[hi]: that comparison is ambiguous on an already-sorted (unrotated) interval, whereas a[hi] always gives a clean signal.
The walkthrough for #06 Find Minimum in Rotated Sorted Array. Watch it, then go straight back and write it yourself.
In a sorted array where every element appears exactly twice except one, you can find the lone element in O(log n) by binary-searching on parity. Before the single element, each pair occupies an even-then-odd index (0-1, 2-3, ...); after it, the alignment shifts to odd-then-even. So at any mid, align it to its pair's even index and ask whether a[mid] == a[mid+1]: if the pairing is intact, the break is to the right; if not, it is here or to the left.
HOW DO YOU FIND THE ONE UNPAIRED ELEMENT IN O(log n), NOT O(n)?
Why align mid to an even index before comparing a[mid] with a[mid+1]?
Alignment makes the parity test meaningful. The invariant is “a[even] == a[even+1]” for every pair before the single element. If mid is odd, comparing a[mid] with a[mid+1] straddles two different pairs and tells you nothing. Nudging mid down to even (mid--) guarantees you are looking at a pair's first element, so the equality check directly answers “is the pairing still normal up to here?” — which is the compass for which half to keep.
On [1, 1, 2, 2, 3, 4, 4, 8, 8], the first mid aligns to index 4 (value 3). Is the pair intact, and where does the search go?
The pair is broken, so the single is here or left. Aligned mid = 4 holds 3, and a[5] = 4 ≠ 3, so the normal even-first pairing has already been disrupted at or before index 4 — the lone element cannot be to the right. Set hi = mid = 4 and continue. Two steps later the interval collapses onto index 4, the single element 3. Note hi = mid, not mid − 1: index 4 itself is a live candidate.
A simpler solution XORs every element together and returns the result. Why might an interviewer reject it here?
XOR is correct but too slow for the stated bound. XOR-ing the whole array cancels every pair and leaves the loner in O(n) time and O(1) space — genuinely elegant, and the right answer to Single Number on an unsorted array. But this problem hands you a sorted array and asks for O(log n), which is a signal that it wants you to exploit the order. Recognising that the sortedness plus a log-n requirement rules out the linear XOR trick is the actual test being set.
Every element is doubled except one. Before the single, each pair sits at an even-then-odd index; after it, the parity flips to odd-then-even. So align mid to its pair's even index and check whether a[mid] == a[mid+1]: intact means the break is to the right, broken means it is here or left. O(log n), and no XOR scan of the whole array.
“Every element appears exactly twice except one”, the array is sorted, and the required complexity is O(log n). That log requirement on a sorted array is the signal: the O(n) XOR trick is not what is being asked for — you are meant to binary-search on the structure the pairing creates.
Before the single element, pairs align even-then-odd; after it, the alignment flips. So at any mid, snap it down to the even index of its pair and check whether a[mid] == a[mid+1]. If they match, the pairing is still normal up to here, so the lone element is to the right (lo = mid + 2). If they do not, the shift has already happened, so the lone element is at mid or to its left (hi = mid). The interval collapses onto the single element.
// Pairs are even-first before the single element, odd-first after it. // Align mid to the pair's even index, then a[mid]==a[mid+1] tells you which // side the parity break -- the lone element -- is on. O(log n), no XOR scan. int singleNonDuplicate(vector<int>& a) { int lo = 0, hi = a.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (mid % 2 == 1) mid--; // align to the even index if (a[mid] == a[mid + 1]) lo = mid + 2; // pairing intact: go right else hi = mid; // pairing broken: here or left } return a[lo]; }
// Pairs are even-first before the single element, odd-first after it. // Align mid to the pair's even index, then a[mid]==a[mid+1] tells you which // side the parity break -- the lone element -- is on. O(log n), no XOR scan. public int singleNonDuplicate(int[] a) { int lo = 0, hi = a.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (mid % 2 == 1) mid--; // align to the pair's first half if (a[mid] == a[mid + 1]) lo = mid + 2; // pairing intact: go right else hi = mid; // broken: single is here or left } return a[lo]; }
# Pairs are even-first before the single element, odd-first after it. # Align mid to the pair's even index, then a[mid]==a[mid+1] tells you which # side the parity break -- the lone element -- is on. O(log n), no XOR scan. def single_non_duplicate(a): lo, hi = 0, len(a) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if mid % 2 == 1: mid -= 1 # align to the even index if a[mid] == a[mid + 1]: lo = mid + 2 # pairing intact: go right else: hi = mid # pairing broken: here or left return a[lo]
Forgetting to align mid to an even index. Without the if (mid % 2 == 1) mid-- nudge, comparing a[mid] with a[mid+1] can straddle two different pairs, and the parity test becomes meaningless — the search wanders and returns a random element. The other temptation is to XOR the whole array: it is correct and elegant but O(n), and the problem's explicit O(log n) requirement exists specifically to rule it out. Reading that requirement as a constraint on your approach, not just your final answer, is the point.
The walkthrough for #07 Single Element in a Sorted Array. Watch it, then go straight back and write it yourself.
The most surprising result in the deck: binary search works on an array that is not sorted at all. A peak is any element greater than both neighbours (the ends count as −∞). At any mid, comparing a[mid] with a[mid+1] reveals a slope — and because the boundaries fall off to negative infinity, walking uphill from anywhere must eventually hit a peak. So discard the downhill side and the interval collapses onto one.
HOW CAN BINARY SEARCH FIND A PEAK WHEN THE ARRAY IS NOT EVEN SORTED?
Binary search usually needs a sorted array. What does the peak problem show it actually requires?
Binary search needs a decidable direction, not sortedness. The real requirement is that, from the middle, you can always prove which half contains a valid answer. A sorted array gives that via value comparison; a peaked array gives it via slope — a[mid] < a[mid+1] proves a peak lies to the right, because you can keep climbing and the boundary is −∞. Internalising this is what lets you spot binary search in problems that never mention sorting — including most of deck 2, where the “array” is a range of candidate answers.
On [1, 3, 5, 4, 2, 6, 7, 0], the first mid is index 3 (value 4), and a[4] = 2. Which way does the search go, and why is that safe?
Left, keeping mid. Since a[3] = 4 > a[4] = 2, the slope falls to the right, which means climbing leftward leads uphill and a peak must exist at mid or to its left (the left boundary is −∞). So hi = mid = 3. It is safe even though 6 and 7 to the right are larger, because the problem asks for any peak, not the global maximum — and index 2 (value 5, a local peak) does lie in the surviving left interval. The MECHANISM slide converges there.
This peak-finder compares a[mid] with a[mid-1] instead of a[mid+1], and reads out of bounds. What is the cleaner fix the standard version uses?
while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] > a[mid - 1]) lo = mid; else hi = mid - 1; }
Compare forward, with the half-open shrink. The clean invariant is lo < hi with hi = mid, which guarantees mid is never the last index, so a[mid+1] is always safe to read — no boundary guard required. Comparing backward to a[mid-1] reads out of bounds at mid = 0 and pairs awkwardly with the shrink direction. The forward comparison plus hi = mid / lo = mid + 1 is why the standard peak search has no edge cases at all.
No sortedness at all, and it still works. a[mid] vs a[mid+1] tells you which way is uphill, and since the ends behave as −∞, walking uphill from anywhere must terminate at a peak. Rising to the right ⇒ a peak lies right; falling ⇒ mid itself could be one. The realisation that binary search does not require a sorted array, only a decidable direction, is the payoff.
“Find a peak / local maximum” and — crucially — the array is not stated to be sorted, yet O(log n) is expected. That combination is the tell that binary search can run on a slope rather than on order: you do not need sortedness, only a rule for which direction leads to an answer.
A peak is an element greater than both neighbours, with the ends treated as −∞ so a peak always exists. At any mid, compare with the next element: if a[mid] < a[mid+1] the slope rises to the right, so a peak lies that way — discard mid and the left. Otherwise the slope falls, so mid itself could be a peak or one lies left — set hi = mid. Following uphill from anywhere must reach a peak, so the interval safely collapses onto one.
// Not sorted -- and binary search still works, because a[mid] vs a[mid+1] // gives a decidable uphill direction, and the ends act as -infinity so a // peak always exists to climb toward. int findPeakElement(vector<int>& a) { int lo = 0, hi = a.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < a[mid + 1]) lo = mid + 1; // uphill is to the right else hi = mid; // mid could be the peak } return lo; }
// Not sorted -- and binary search still works, because a[mid] vs a[mid+1] // gives a decidable uphill direction, and the ends act as -infinity so a // peak always exists to climb toward. public int findPeakElement(int[] a) { int lo = 0, hi = a.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < a[mid + 1]) lo = mid + 1; // uphill is to the right else hi = mid; // downhill: peak is mid or left } return lo; // lo == hi: a peak }
# Not sorted -- and binary search still works, because a[mid] vs a[mid+1] # gives a decidable uphill direction, and the ends act as -infinity so a # peak always exists to climb toward. def find_peak_element(a): lo, hi = 0, len(a) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if a[mid] < a[mid + 1]: lo = mid + 1 # uphill is to the right else: hi = mid # mid could be the peak return lo
Reading a[mid − 1] or a[mid + 1] without guarding the boundary. The clean fix is the half-open loop lo < hi with hi = mid, which guarantees mid is never the last index, so a[mid + 1] is always in range — no special cases. The conceptual trap is assuming you need the global maximum: the problem asks for any peak, which is what makes the O(log n) slope-following valid; hunting the global max would force O(n).
The walkthrough for #08 Find Peak Element. Watch it, then go straight back and write it yourself.
When a matrix has every row sorted and the first element of each row larger than the last of the previous row, reading it top-to-bottom, left-to-right yields one long sorted sequence. So it is not really 2D at all — binary search the flat index range [0, m·n − 1] and convert each midpoint back with row = mid / cols, col = mid % cols. Ordinary binary search, plus one line of index arithmetic.
HOW DO YOU SEARCH A FULLY SORTED MATRIX WITHOUT WRITING ANY 2D LOGIC?
Why can Search a 2D Matrix (I) be solved as a single 1D binary search, while Matrix II cannot?
Global ordering across the row seams. The flatten trick treats the matrix as row0 ++ row1 ++ …, and that concatenation is sorted only if each row starts higher than the previous row ended — which Matrix I guarantees and Matrix II does not. In Matrix II a row can start lower than a cell in the row above, so the flattened sequence has descents and binary search on it is invalid. Recognising which of the two ordering guarantees you have is the whole choice between the two problems.
In a 3×4 matrix, binary search picks flat index mid = 6. Which cell (row, col) is that?
(1, 2). With 4 columns, row = 6 / 4 = 1 and col = 6 % 4 = 2. The division counts how many full rows fit below index 6, and the remainder is the offset within that row. This single line is the entire adaptation — everything else is the plain binary search from unit 1. The MECHANISM slide shows the flat midpoint lighting the corresponding grid cell each step.
A variant gives you the matrix as a true 2D structure but asks you not to allocate a flattened copy. Does the trick still apply?
Yes — the flattening is virtual. You never construct a 1D array; you binary-search the index range [0, m·n − 1] and, each time you need the value at mid, compute m[mid / cols][mid % cols] on the fly. That is O(1) extra space and O(log mn) time. The insight worth keeping is that “flatten” is a way of thinking about the index space, not an instruction to copy memory.
When a matrix is fully sorted — each row ascending and every row's first element larger than the previous row's last — reading it left-to-right, top-to-bottom gives one long sorted sequence. So do not think in 2D at all: binary search the flat index range [0, m·n−1], and convert each midpoint back with row = mid / cols, col = mid % cols. Ordinary binary search, one line of index arithmetic.
A matrix that is fully sorted — each row ascending, and the first entry of every row greater than the last of the row above — with a target to locate in O(log mn). That global ordering across the row seams is the specific signal for the flatten trick; it is what separates this from Matrix II.
Because the rows chain together into one sorted sequence, treat the matrix as a virtual 1D array of length m·n and run plain binary search on the index range [0, m·n − 1]. Whenever you need the value at a midpoint, recover its cell with row = mid / cols and col = mid % cols. No copy is made; the flattening is purely a way of indexing.
// Fully sorted matrix = one sorted array of length m*n. Binary search // the flat index; recover the cell with row = mid/cols, col = mid%cols. bool searchMatrix(vector<vector<int>>& m, int t) { int R = m.size(), C = m[0].size(); int lo = 0, hi = R * C - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int v = m[mid / C][mid % C]; // flatten the index if (v == t) return true; if (v < t) lo = mid + 1; else hi = mid - 1; } return false; }
// Fully sorted matrix = one sorted array of length m*n. Binary search // the flat index; recover the cell with row = mid/cols, col = mid%cols. public boolean searchMatrix(int[][] m, int t) { int R = m.length, C = m[0].length; int lo = 0, hi = R * C - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int v = m[mid / C][mid % C]; // flatten the index if (v == t) return true; if (v < t) lo = mid + 1; else hi = mid - 1; } return false; }
# Fully sorted matrix = one sorted array of length m*n. Binary search # the flat index; recover the cell with row = mid//cols, col = mid%cols. def search_matrix(m, t): R, C = len(m), len(m[0]) lo, hi = 0, R * C - 1 while lo <= hi: mid = lo + (hi - lo) // 2 v = m[mid // C][mid % C] # flatten the index if v == t: return True if v < t: lo = mid + 1 else: hi = mid - 1 return False
Applying the flatten to Matrix II. The whole trick rests on each row starting higher than the previous row ended; Matrix II makes no such promise, so its concatenated rows are not globally sorted and binary search on the flat index silently returns wrong answers. The other slip is the index math — mixing up mid / cols and mid % cols, or using rows instead of columns as the divisor. It is cols that divides, because rows are laid end to end.
The walkthrough for #09 Search a 2D Matrix. Watch it, then go straight back and write it yourself.
Matrix II is only row- and column-sorted, so it cannot be flattened. But start at the top-right corner and something clean happens: that cell is the largest in its row and the smallest in its column. So one comparison always eliminates an entire line — too big means the whole column below is bigger (drop the column); too small means the whole row to the left is smaller (drop the row). Each step removes a row or a column, giving O(m + n).
HOW DO YOU SEARCH A ROW- AND COLUMN-SORTED MATRIX THAT WON'T FLATTEN?
Why start at the top-right corner rather than the top-left?
The top-right corner is a monotone pivot. Being the largest in its row and smallest in its column means: if it is bigger than the target, every cell below it (same column) is also bigger, so the column is useless — drop it. If it is smaller, every cell to its left (same row) is also smaller — drop the row. The top-left corner is the minimum of both its row and column, so “too small” could send you right OR down with no way to choose. Bottom-left works too (min of row, max of column); the two 'mixed' corners are the valid starts.
Searching for 5 in [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]] from the top-right, what are the first three cells visited?
(0,3)=11 → (0,2)=7 → (0,1)=4. Start at 11 (top-right): 11 > 5, drop the column, move left to 7; 7 > 5, drop the column, move to 4; 4 < 5, now drop the row and move down to (1,1)=5 — found. The path is a staircase hugging the boundary between values below and above the target, which is exactly why it is O(m + n): it can traverse at most m rows down and n columns left. The MECHANISM slide traces this path and greys the eliminated rows and columns.
This staircase search starts at the bottom-right corner. Why does it fail?
int r = m.size() - 1, c = m[0].size() - 1; // bottom-right while (r >= 0 && c >= 0) { if (m[r][c] > t) c--; else r++; }
Bottom-right is the global maximum of its row and column, so it is not a pivot. When m[r][c] > t, both the cell above and the cell to the left could contain the target, and you cannot rule out a whole line — the elimination that makes the algorithm work is impossible. The valid starting corners are the two “mixed” ones: top-right (max row / min col) or bottom-left (min row / max col). The corner choice is not cosmetic; it is what creates the decisive comparison.
Matrix II is only row- and column-sorted, so the flatten trick fails. Instead start at the top-right corner: that cell is the largest in its row and the smallest in its column, which makes every comparison decisive. Too big? Everything below it in the column is bigger too — drop the column. Too small? Everything left in the row is smaller — drop the row. Each step removes a whole line, so it is O(m + n).
A matrix sorted along rows and down columns, but not globally — so no flatten. The staircase signal is exactly this weaker ordering plus a target to find; the expected complexity O(m + n) is the tell that you eliminate a whole line per step rather than halving.
Start at the top-right corner, which is the maximum of its row and the minimum of its column — a monotone pivot. Compare it to the target: if it is too big, every cell below it in the column is also too big, so drop the column (move left); if it is too small, every cell to its left in the row is smaller, so drop the row (move down). Each step removes an entire row or column, so the walk is O(m + n).
// Row- and column-sorted, but not globally -- so flattening fails. // Start TOP-RIGHT: max of its row, min of its column, so each comparison // eliminates a whole line. O(m + n). bool searchMatrix(vector<vector<int>>& m, int t) { int r = 0, c = m[0].size() - 1; // top-right corner while (r < (int)m.size() && c >= 0) { if (m[r][c] == t) return true; if (m[r][c] > t) c--; // too big: drop the column else r++; // too small: drop the row } return false; }
// Row- and column-sorted, but not globally -- so flattening fails. // Start TOP-RIGHT: max of its row, min of its column, so each comparison // eliminates a whole line. O(m + n). public boolean searchMatrix(int[][] m, int t) { int r = 0, c = m[0].length - 1; // top-right corner while (r < m.length && c >= 0) { if (m[r][c] == t) return true; if (m[r][c] > t) c--; // too big: drop this COLUMN else r++; // too small: drop this ROW } return false; }
# Row- and column-sorted, but not globally -- so flattening fails. # Start TOP-RIGHT: max of its row, min of its column, so each comparison # eliminates a whole line. O(m + n). def search_matrix(m, t): r, c = 0, len(m[0]) - 1 # top-right corner while r < len(m) and c >= 0: if m[r][c] == t: return True if m[r][c] > t: c -= 1 # too big: drop the column else: r += 1 # too small: drop the row return False
Starting at the wrong corner. Top-left and bottom-right are the minimum and maximum of both their row and column, so a comparison there cannot single out a line to eliminate — the algorithm stalls or wanders. Only the two mixed corners work: top-right or bottom-left. The second trap is reaching for the flatten trick out of habit; it needs global ordering that this matrix does not have, and it fails on the very first row seam where a lower row starts below the row above it.
The walkthrough for #10 Search a 2D Matrix II. Watch it, then go straight back and write it yourself.
A 2D peak is a cell greater than all four of its neighbours, and — exactly as in 1D — you do not need the matrix sorted, only a climbable direction. Binary search the columns: in the middle column, find the row holding its maximum. If that cell also beats its left and right neighbours it is a peak; if not, the larger horizontal neighbour points to a half of columns that must contain one. Taking the column's maximum is what guarantees you never need to search up or down.
HOW DO YOU FIND A 2D PEAK IN O(m log n) WITHOUT SCANNING EVERY CELL?
Within the chosen middle column, why take the row with the column's MAXIMUM rather than any cell?
Taking the column maximum collapses the 2D problem to 1D. A peak must exceed all four neighbours; by picking the largest cell in the column you have already guaranteed it beats the cells above and below it, so the only remaining question is the horizontal one — is a left or right neighbour bigger? That is precisely the 1D peak decision, and following the larger side must reach a peak because the column-max envelope keeps rising. Without taking the max, a vertical neighbour could exceed your cell and the slope argument would break.
In [[10,20,15],[21,30,14],[7,16,32]], the search starts at the middle column (index 1). What is the column's max, and is it a peak?
30 at (1,1) is a peak. Column 1 holds 20, 30, 16, so its maximum is 30 at row 1. Its horizontal neighbours are m[1][0] = 21 and m[1][2] = 14, both smaller — and because 30 is the column max it already beats m[0][1] = 20 and m[2][1] = 16 above and below. All four neighbours are smaller, so 30 is a valid 2D peak and the search returns immediately. One column examined, no descent into rows above or below.
Why is the complexity O(m log n) and not O(log m · log n)?
Finding a column's maximum is an O(m) linear scan, not a binary search. The columns are not sorted, so there is no way to locate the maximum faster than looking at all m entries. Binary search still applies to which column — that gives the log n factor — but each of those log n probes pays O(m) for its column scan, hence O(m log n). Recognising exactly which dimension supports binary search and which forces a scan is what pins down the complexity.
A 2D peak beats all four neighbours, and — as in 1D — you do not need sortedness, only a climbable direction. Binary search the columns: in the middle column find the row holding its maximum. If that cell beats its left and right neighbours it is a peak; otherwise the larger neighbour points to a half that must contain one, because the column max guarantees you never need to look up or down. O(m log n).
“Find any peak in a matrix” — a cell strictly greater than its four neighbours — with a better-than-O(mn) bound expected. As in the 1D peak problem, the absence of any sortedness requirement plus a sub-linear target is the signal that binary search runs on a slope, here across columns.
Binary search the columns. In the middle column, scan for the row holding its maximum; that cell already beats its vertical neighbours, so only its horizontal neighbours matter. If it beats both, it is a peak. Otherwise the larger horizontal neighbour lies in a half of columns that must contain a peak — because following the rising column-maxima cannot run off the edge without cresting. Discard the other half and repeat.
// A 2D peak beats all four neighbours. Binary search the COLUMNS; in each, // take the row with the column's max -- that already beats up/down, so only // left/right decide. Follow the larger neighbour. O(m log n). vector<int> findPeakGrid(vector<vector<int>>& m) { int lo = 0, hi = m[0].size() - 1; while (lo <= hi) { int mc = lo + (hi - lo) / 2; int mr = 0; // row of the column max for (int i = 1; i < (int)m.size(); i++) if (m[i][mc] > m[mr][mc]) mr = i; int L = mc ? m[mr][mc - 1] : -1; int Rn = mc + 1 < (int)m[0].size() ? m[mr][mc + 1] : -1; if (m[mr][mc] > L && m[mr][mc] > Rn) return {mr, mc}; else if (Rn > m[mr][mc]) lo = mc + 1; // climb right else hi = mc - 1; // climb left } return {-1, -1}; }
// A 2D peak beats all four neighbours. Binary search the COLUMNS; in each, // take the row with the column's max -- that already beats up/down, so only // left/right decide. Follow the larger neighbour. O(m log n). public int[] findPeakGrid(int[][] m) { int lo = 0, hi = m[0].length - 1; while (lo <= hi) { int mc = lo + (hi - lo) / 2; int mr = 0; for (int r = 0; r < m.length; r++) // the column's max row if (m[r][mc] > m[mr][mc]) mr = r; int left = (mc > 0) ? m[mr][mc - 1] : -1; int right = (mc < m[0].length - 1) ? m[mr][mc + 1] : -1; if (m[mr][mc] > left && m[mr][mc] > right) return new int[]{mr, mc}; if (left > m[mr][mc]) hi = mc - 1; // climb left else lo = mc + 1; // climb right } return new int[]{-1, -1}; }
# A 2D peak beats all four neighbours. Binary search the COLUMNS; in each, # take the row with the column's max -- that already beats up/down, so only # left/right decide. Follow the larger neighbour. O(m log n). def find_peak_grid(m): lo, hi = 0, len(m[0]) - 1 while lo <= hi: mc = lo + (hi - lo) // 2 mr = max(range(len(m)), key=lambda i: m[i][mc]) # row of column max L = m[mr][mc - 1] if mc > 0 else -1 Rn = m[mr][mc + 1] if mc + 1 < len(m[0]) else -1 if m[mr][mc] > L and m[mr][mc] > Rn: return [mr, mc] elif Rn > m[mr][mc]: lo = mc + 1 # climb right else: hi = mc - 1 # climb left return [-1, -1]
Comparing an arbitrary cell instead of the column's maximum. The slope argument only holds for the largest cell in the column — that is what guarantees the vertical neighbours are already beaten, so a larger horizontal neighbour reliably points toward a peak. Pick any other cell and a vertical neighbour might exceed it, breaking the invariant and sending the search to a column with no peak. The second trap is expecting O(log m · log n): the column is unsorted, so locating its maximum is an unavoidable O(m) scan, making the true cost O(m log n).
The walkthrough for #11 Find a Peak Element II. Watch it, then go straight back and write it yourself.
“A sorted array was rotated an unknown number of times; find the value at the k-th position of the original.” What is the key sub-problem?
Find the minimum, which is the rotation offset. The index of the minimum is exactly how many places the array was rotated, and it is found in O(log n) by comparing a[mid] to a[hi]. Once you know the offset, the original index k maps to (offset + k) % n in the rotated array. This is why find-min is a load-bearing primitive, not a one-off: the rotation count it returns unlocks a family of rotated-array questions.
You are told an array is sorted and asked for the number of elements strictly less than a target. Which primitive, in one call?
lower_bound(target). It returns the first index with a[i] ≥ target — and because everything before that index is strictly less than the target, that index is the count. No scan, no subtraction. Recognising that lower_bound's return value doubles as a count (and upper_bound − lower_bound is the number of occurrences) is what turns it from a search into a Swiss-army primitive.
Binary search is short, which is exactly why its bugs are subtle — an overflow, a non-shrinking interval, a boundary off by one. Every one of these compiles and returns a plausible answer.
(lo + hi) / 2 wraps negative when both indices are large — routine in binary-search-on-answers, where hi can be 10⁹ or more. Always lo + (hi − lo) / 2. Silent: it produces a bad index, not a compile error.
If one branch keeps mid in the interval, the other must move past it (mid ± 1). Two branches that both keep mid can leave the interval the same size forever — an infinite loop on adjacent lo, hi.
Plain search returns an occurrence, not the first. For boundary problems you must record the hit and keep narrowing. Returning early passes the single-occurrence tests and fails on duplicates.
In find-min and peak, mid itself can be the answer, so the shrink is hi = mid, not mid − 1. Using mid − 1 can step over the very element you want — a plausible wrong answer on rotated or peaked input.
With duplicates, a[lo] == a[mid] == a[hi] makes it impossible to tell which half is sorted. You must shrink both ends by one, which drops the guarantee to O(n) worst case. Search II is exactly this case, and forgetting it gives wrong answers on [3,1,3,3,3].
Search-a-2D-Matrix I is fully sorted when flattened (treat it as one array of length m·n); Matrix II is only row- and column-sorted (walk the staircase from a corner). Applying the flatten trick to II gives wrong answers — the row boundaries do not line up.
Eleven searches, one collapse. The right-hand column is the recognition — the question asked at mid — which is the part that is actually hard.
Once the interval-collapse invariant is automatic, the answer-space reframe in deck 2 stops looking like a different technique and starts looking like the same one pointed at a range of numbers instead of an array.
Lectures are Striver's A2Z DSA course. Problem links are LeetCode. 10 units from the 29-lecture playlist; the answer-space problems are deck 2.
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.