Binary search is the algorithm everyone knows and almost nobody writes correctly on the first try. The reason is not the idea, which is two lines. It is that every failure mode is silent: no crash, no timeout, just a wrong index.
This is the first of three posts working through Joseph Choi’s binary search session deck in C++. Between them they cover twenty-two LeetCode problems, and they are split by the only question that matters — where does the monotonicity come from? This post takes the ten problems where it comes from the sort order, and sets up the two templates the other two posts reuse.
Everything here was compiled with -Wall -Wextra -fsanitize=undefined,address and checked against a brute-force implementation before the prose was written. The numbers in the closing section — iteration counts, API probe ranges, failure rates for the wrong bound — are measured, not estimated.
The one idea: stop looking for the target
Most people learn binary search as “find a value in a sorted array.” That description is true and almost useless, because it fits exactly one of the twenty-two problems these three posts cover. Four of them have no array. Three have no target. Two have an array that is not sorted.
The framing that fits all of them is this one:
You have a range of candidate indices and a yes/no question you can ask about any single one of them. The answers are false, false, …, false, true, true, …, true — once the answer flips, it never flips back. Binary search finds where it flips.
That property — the answers are sorted even if the data is not — is called monotonicity, and it is the only thing binary search actually requires. A sorted array is just the most common way to get it: “is nums[i] at least the target?” is false up to a point and true after it. But “can Koko finish the piles at speed i?” is monotone too, and there is no array of speeds anywhere.
So the question to ask of a new problem is never “is this array sorted?” It is: what is the yes/no question, and is its answer monotone? That question has three common answers, and they are the three posts:
- The sort order gives it to you. Ten problems, below.
- The array is not sorted, and some other structure gives it to you — a local comparison against a neighbour, or a fixed reference point in a rotated array. Seven problems, in part two.
- There is no array. You invent the search space out of the possible answers and test each candidate for feasibility. Five problems, in part three.
If “throw half the search space away” sounds familiar, it is the same instinct as decrease and conquer — binary search is that idea’s most disciplined case, where the half you discard is exactly half.
The two templates
Write these two until they are muscle memory. Every solution in all three posts is one of them with a different predicate.
Template A: the closed interval
// Returns the first index in [lo, hi] where pred is true, or hi + 1 if there is none.
// On exit lo == hi + 1 always: lo is the first true, hi is the last false.
int firstTrue(int lo, int hi, const function<bool(int)>& pred) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // never lo + hi: that can overflow
if (pred(mid)) hi = mid - 1; // mid might be the answer, but look left for an earlier one
else lo = mid + 1; // mid is definitely not the answer
}
return lo;
}This is the shape the deck uses everywhere, and it has one property that explains every return statement in the next 4,000 words:
When a
while (lo <= hi)loop exits,lo == hi + 1, always. They cross by exactly one. Solois the first index where the predicate is true, andhiis the last index where it is false.
Both halves of that sentence are useful, and which one you want depends on the problem. First Bad Version wants the first true, so it returns start. sqrt(x) wants the largest number whose square still fits, which is the last false, so it returns end. Arranging Coins returns end. Koko returns startK. Missing Element indexes with nums[end]. Once you know the invariant you never have to reason about the final ±1 again — you just ask yourself which side of the boundary you want. I verified the invariant on 200,000 randomly generated ranges and predicates, including the degenerate cases where the answer is outside the range entirely.
Template B: the converging interval
// Keeps one candidate alive at all times and returns it. Use when there is no
// "is this it?" test you can apply to a single index in isolation.
int converge(int lo, int hi, const function<bool(int)>& keepLeft) {
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // mid < hi, so mid + 1 is always in range
if (keepLeft(mid)) hi = mid; // mid stays a candidate
else lo = mid + 1;
}
return lo;
}Template A needs a predicate you can evaluate at a single index in isolation. Sometimes you do not have one: for the peak problems, “is this the peak?” needs both neighbours, and for the rotated-array problems the only meaningful comparison is against the other end of the live window. Template B handles those by never discarding the current candidate — hi = mid, not hi = mid - 1 — so exactly one index survives and the loop ends with lo == hi.
The deck states this invariant in its own words on the Find Peak Element slide: keep narrowing correctly, and when left == right that index must be the answer. Two mechanical details make it work. Because the loop condition is strict, mid < hi always, so mid + 1 is in range without a bounds check — that is why the peak solutions need no guard clauses. And because lo = mid + 1 always moves, the loop cannot spin forever; write lo = mid in template B and you get an infinite loop on a two-element window.
The middle index
int mid = (lo + hi) / 2; // overflows: with lo=1, hi=2147483647 this is -1073741824
int mid = lo + (hi - lo) / 2; // safe: the difference always fits, and mid stays in [lo, hi]
int mid = lo + ((hi - lo) >> 1); // same thing; no faster on any compiler from this decadeThe deck writes start + (end - start) / 2 in all twenty-two of its solutions, and that consistency is worth copying rather than treating as a stylistic tic. Two of these problems genuinely need it: First Bad Version allows n up to 231 − 1, and Arranging Coins allows the same. With lo = 1 and hi = 2147483647, (lo + hi) / 2 evaluates to −1073741824 and your next array access is a negative index. The subtraction form can never overflow, because a difference of two values in range is in range.
Those three blocks are the whole toolkit. The remaining twenty-two problems, across all three posts, are one of the two templates with a different predicate in the middle.
Part 1: when the array itself is the predicate
Six problems where the yes/no question is a direct comparison against the data. This is the family everyone already half-knows, so the interesting content is in what each one does after the loop.
Guess Number Higher or Lower (LC 374, Easy)
The deck calls this a typical binary search problem and moves on, which is fair. It is worth one slide because it strips the problem down to nothing: no array at all, just a range 1…n and an oracle that tells you high, low, or correct.
int guessNumber(int n) {
int start = 1, end = n;
while (start <= end) {
int mid = start + (end - start) / 2;
int verdict = guess(mid); // one call, not two
if (verdict == 0) return mid;
if (verdict == -1) end = mid - 1; // my guess was too high
else start = mid + 1;
}
return -1; // unreachable: the problem guarantees a hit
}One change from the deck: cache the verdict. The deck calls guess(mid) twice in the worst case, once to test for zero and once to test for −1. On LeetCode that is free, but in this problem the oracle is the cost model — it is the only thing you are being charged for — and two problems later (Search in a Sorted Array of Unknown Size) the call count becomes the thing the grader actually limits.
First Bad Version (LC 278, Easy)
Here the deck’s framing arrives properly: there is no target to find. There are two zones — good versions, then bad versions — and you want the boundary. That is the whole series in one problem.
int firstBadVersion(int n) {
int start = 1, end = n; // versions are 1..n; starting at 0 probes a version that does not exist
while (start <= end) {
int mid = start + (end - start) / 2; // n can be 2^31 - 1, so this form is mandatory
if (isBadVersion(mid)) end = mid - 1;
else start = mid + 1;
}
return start; // first true
}The predicate is handed to you as an API. isBadVersion is false, false, …, true, true, and start is the first true. Nothing else is needed.
I changed one character from the deck, which prints int start = 0;:
int start = 0; // as printed in the deck
int end = n;
// Versions are numbered 1..n. With n = 1 the first probe is mid = 0, so the
// judge's isBadVersion is asked about a version that does not exist. The
// returned answer is still right, because "version 0 is not bad" happens to
// be what the mock replies -- but it is a call the problem never promised
// to answer.Instrumenting the mock API confirms it: over every combination of n and first-bad-version up to 80, the deck’s version probes versions in the range [0, 80] while the valid range is [1, 80]. The answer still comes out right, because “version 0 is not bad” is what a reasonable mock replies. But it is a call outside the contract, and on a real system — where version 0 might be a 404 rather than a false — that is the kind of thing that turns into an incident. Starting at 1 costs nothing.
Search Insert Position (LC 35, Easy)
The deck’s note is exactly right: when the target does not exist you need the first index whose value is not smaller than the target. That is a lower bound, and it is the single most reusable predicate in this whole series.
int searchInsert(vector<int>& nums, int target) {
int start = 0, end = (int)nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) end = mid - 1; // predicate: "nums[mid] is at least target"
else start = mid + 1;
}
return start; // first index not smaller than target
}The deck’s version has a three-way branch with an early return mid on an exact match. That is correct for this problem, but only because LC 35 promises distinct values: on [1,2,2,2,3] with target 2 it returns index 2, while a lower bound returns 1. The two-branch version above has no such dependency — I checked it against std::lower_bound on 8,000 random arrays including duplicates and it agrees every time. Since the next three problems all need a real lower bound, learning the two-branch form here saves you from learning it twice.
Find Smallest Letter Greater Than Target (LC 744, Easy)
Two zones, says the deck: letters at most the target, then letters greater than it. Find the first letter of the second zone. The predicate is letters[mid] > target — an upper bound rather than a lower bound, which is the difference of one character.
char nextGreatestLetter(vector<char>& letters, char target) {
int start = 0, end = (int)letters.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (letters[mid] > target) end = mid - 1;
else start = mid + 1;
}
return letters[start % letters.size()]; // wraps when every letter is <= target
}The only thing that makes this problem more than a template instance is the wrap-around. If every letter is at most the target, the second zone is empty and start lands at letters.size(). The modulo sends it back to index 0, which is what the problem asks for — the letters are treated as a cycle. Writing it as start % letters.size() rather than an if is a small thing, but it makes the cyclic intent visible instead of looking like an out-of-range patch.
Find First and Last Position of Element in Sorted Array (LC 34, Medium)
The deck’s note: run binary search twice, two zones for each. That is exactly it — the first and last positions of a run are two different boundaries, and each needs its own predicate.
int lowerBound(const vector<int>& nums, int target) { // first index with nums[i] >= target
int start = 0, end = (int)nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) end = mid - 1; else start = mid + 1;
}
return start;
}
int upperBound(const vector<int>& nums, int target) { // first index with nums[i] > target
int start = 0, end = (int)nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] > target) end = mid - 1; else start = mid + 1;
}
return start;
}
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lowerBound(nums, target);
if (lo == (int)nums.size() || nums[lo] != target) return {-1, -1};
return {lo, upperBound(nums, target) - 1};
}The two helpers differ by one character, >= versus >, and that character is the difference between “first element not below the target” and “first element strictly above it.” The last index of the run is one before the upper bound.
The check on line three of searchRange is the part worth slowing down for. A lower bound always returns something — it is an insertion point, not a match — so it comes back as nums.size() when the target is bigger than everything, and as the index of some larger element when the target is absent from the middle. Both cases have to be rejected explicitly, and the lo == nums.size() test must come first or the nums[lo] read is out of bounds. Note also that this version needs no empty-array guard: with nums.empty(), lowerBound returns 0, 0 == nums.size() is true, and the function returns {-1, -1} without ever touching the array.
Check If a Number Is Majority Element in a Sorted Array (LC 1150, Easy, Premium)
Note: LC 1150 is a LeetCode Premium problem, viewable only with a paid subscription. Given a sorted array and a target, return whether the target occurs more than n/2 times.
The deck’s route is to find the first index of the target and then check whether “the other index” is still the target. Making that precise gives a two-line solution with no counting at all.
bool isMajorityElement(vector<int>& nums, int target) {
int n = nums.size();
int first = lowerBound(nums, target);
int mirror = first + n / 2; // n/2 steps further into the run
return mirror < n && nums[mirror] == target; // n/2 + 1 copies means strictly more than half
}The run of copies is contiguous because the array is sorted, so it occupies indices first … first + count - 1. Asking whether nums[first + n/2] is still the target is asking whether count ≥ n/2 + 1, and n/2 + 1 > n/2 for both parities of n — for odd n because integer division rounds down, for even n trivially. So one array read answers the majority question, and the mirror < n guard handles both “the target is absent” and “the run is too short,” since in either case the mirror index either overshoots the array or lands on a different value.
Worth appreciating: this is a genuine O(log n) answer to a question that looks like it needs a count. The linear scan is easier to write and, at these constraints, faster in practice. The binary search is what you would want if the array lived on disk.
Part 2: still sorted, but the sequence needs building
Four problems where the data is sorted and the monotone sequence is still not sitting in front of you. One hides it in two dimensions, one will not tell you how long it is, one has no useful value comparison at all, and one needs a quantity that is nowhere in the array. In each case the work is constructing the sequence; the search itself is template A again.
Search a 2D Matrix (LC 74, Medium)
The deck asks the right question: is it possible to treat the 2D array like a 1D array? It is, and noticing that is the entire problem.
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size(), cols = matrix[0].size();
int start = 0, end = rows * cols - 1; // treat the matrix as one flat sorted array
while (start <= end) {
int mid = start + (end - start) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) return true;
if (value < target) start = mid + 1; else end = mid - 1;
}
return false;
}Binary search does not need an array. It needs a totally ordered sequence you can index in O(1), and matrix[i / cols][i % cols] is exactly that: a virtual array of length rows × cols, sorted because each row is sorted and every row starts above the previous row’s end. No data is copied.
Two habits to note. Hoisting rows and cols into int locals is what keeps rows * cols - 1 out of unsigned arithmetic — matrix.size() * matrix[0].size() - 1 would be computed in size_t, which is fine here but is the same shape as bugs elsewhere in these posts. And the division and modulo must use the same cols; deriving row from one dimension and col from the other is the classic way to get a solution that passes the square test cases and fails the rectangular ones.
Search in a Sorted Array of Unknown Size (LC 702, Medium, Premium)
Note: also Premium. You get an ArrayReader with a single method get(index), which returns 231 − 1 for any index past the end. The length is not given.
This is the problem that forces the point. Binary search cannot start without an upper bound, so if you do not have one, manufacture one — and the deck’s answer is the right one: start the end index at 1 and double it.
int searchUnknownSize(const ArrayReader& reader, int target) {
int end = 1; // phase 1: find a bound that overshoots
while (reader.get(end) < target) end *= 2; // get() returns INT_MAX past the end, which stops this
int start = end / 2; // everything below end/2 was already ruled out
while (start <= end) { // phase 2: ordinary binary search
int mid = start + (end - start) / 2;
int value = reader.get(mid);
if (value == target) return mid;
if (value < target) start = mid + 1; else end = mid - 1;
}
return -1;
}Doubling until you overshoot is called exponential or galloping search. It costs O(log n) probes to find a bound and then O(log n) to search inside it, so the total is still logarithmic — you have paid a factor of two, not a factor of n.
The out-of-range sentinel is doing quiet work here. Because get returns a value larger than any real element, the doubling loop needs no separate length check: overshooting the array looks exactly like overshooting the target. The deck adds an explicit != INT_MAX test, which is harmless but redundant given that the problem caps values at 104.
One small tightening over the deck, which starts the second phase at 0: when the doubling loop stops, you already know that get(end / 2) was below the target, so the answer cannot be at or below end / 2. Starting there instead saves a probe or two, and in a problem whose whole point is that get is expensive, that is the right instinct. Measured on arrays up to length 20, the version above never needs more than 10 reads.
Single Element in a Sorted Array (LC 540, Medium)
Every element appears twice except one; find it in O(log n). The array is sorted, but there is no target and no value comparison that helps — the monotone quantity here is not a value at all. It is an alignment.
Before the single element, every pair starts at an even index: positions (0,1), (2,3), (4,5). After it, that is knocked out of step and every pair starts at an odd index. So “are the pairs still aligned at this position?” is true, true, …, false, false — monotone, which is all template B needs.
int singleNonDuplicate(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) --mid; // always compare a pair starting at an even index
if (nums[mid] == nums[mid + 1]) lo = mid + 2; // pairs still line up: the odd one out is further right
else hi = mid; // alignment already broken: it is at or before mid
}
return nums[lo];
}Forcing mid to be even is not a detail, it is the algorithm. Without it, nums[mid] == nums[mid + 1] compares the second element of one pair with the first element of the next, which tells you nothing. I ran both versions over 50,000 valid arrays: with the alignment, zero failures; without it, 24,072 failures. This is the sort of bug that passes [1,1,2] and dies on the fourth test case.
The deck takes a different and equally valid route: check whether the answer is at position 0 or at the end, and only then run a loop that compares nums[mid] against both neighbours.
// as printed in the deck: rule out the three easy positions first, then the
// loop can safely touch nums[mid - 1] and nums[mid + 1] without any bounds test
if (nums.size() == 1) return nums[0];
if (nums[0] != nums[1]) return nums[0];
if (nums[nums.size() - 1] != nums[nums.size() - 2]) return nums[nums.size() - 1];Those three guards look like ordinary boilerplate for trivial inputs, and they are not — they are what makes the unguarded nums[mid - 1] and nums[mid + 1] inside the loop safe. Once you know the single element is strictly interior and that nums[0] == nums[1], you can prove mid never reaches either end: it would require three consecutive equal values, which cannot happen when every value appears at most twice. I ran the deck’s version under the address sanitizer across 20,000 arrays with no out-of-bounds read, which is the evidence, not the proof. The parity version needs no such argument, which is why I prefer it.
Missing Element in Sorted Array (LC 1060, Medium, Premium)
Note: Premium again. Given a strictly increasing array and an integer k, return the k-th number missing from the array, counting up from nums[0].
The deck gives away the trick in one line: at index i, the number of values missing to the left is nums[i] - (nums[0] + i). If nothing were missing, index i would hold nums[0] + i; every gap pushes the value one higher than its slot. So the difference counts the gaps.
int missingElement(vector<int>& nums, int k) {
int n = nums.size();
auto missingBefore = [&](int i) { return nums[i] - nums[0] - i; }; // gaps to the left of index i
int start = 0, end = n - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (missingBefore(mid) >= k) end = mid - 1; else start = mid + 1;
}
// end is the last index with fewer than k missing before it
return nums[end] + (k - missingBefore(end));
}That quantity is non-decreasing in i, which makes “are there at least k missing before here?” a monotone predicate with no array to sort and no value to compare. This is the clearest example in the deck of the general move: when the data is not monotone in the way you need, compute something that is.
After the loop, end is the last index with fewer than k missing before it — the last false. From there you walk forward: k - missingBefore(end) more gaps are still owed, and since everything after end is one unbroken run of missing numbers, you add that count to nums[end]. Note that end can never go below 0: at mid == 0 the missing count is 0, and k ≥ 1, so the first probe always moves start rather than end.
The ten problems on one page
| Problem | Search space | Predicate at mid | Template | Returns |
|---|---|---|---|---|
| 374 Guess Number | 1…n | oracle: too high? | A | mid on a hit |
| 278 First Bad Version | 1…n | isBadVersion(mid) | A | start |
| 35 Search Insert | indices | nums[mid] >= target | A | start |
| 744 Smallest Letter | indices | letters[mid] > target | A | letters[start % n] |
| 34 First and Last Position | indices, twice | >= target, then > target | A | {lo, upper - 1} |
| 1150 Majority Element | indices | nums[mid] >= target | A | nums[first + n/2] == target |
| 74 Search 2D Matrix | 0…rows·cols−1 | flattened cell vs target | A | true on a hit |
| 702 Unknown Size | built by doubling | get(mid) vs target | A | mid on a hit |
| 540 Single Element | indices | pairs still aligned? | B | nums[lo] |
| 1060 Missing Element | indices | missingBefore(mid) >= k | A | computed from nums[end] |
Read down the predicate column. That is the only column where the problems actually differ — everything else is the template.
Misfits, edge cases, and the things that bite
Everything below was measured by running it, not by reasoning about it. The two items in this section that apply to every binary search live here because this is the foundation post; parts two and three point back at them.
The predicate has to be monotone, and nothing checks that for you
auto pred = [](int i) { return i == 3 || i >= 6; }; // true, false, ..., true
firstTrue(0, 9, pred); // returns 6; the first true index is actually 3This is the failure mode with no symptoms. The loop terminates, returns a plausible index, and is wrong. Every one of the twenty-two solutions across these three posts rests on an unstated monotonicity argument, and when you adapt one to a new problem, that argument is the thing you have to re-check — not the loop bounds.
A practical test: state the predicate as a sentence, then ask whether making the index larger could ever turn a true back into a false. “Is nums[i] ≥ target in a sorted array” — no. “Can Koko finish at speed i” — no, faster never hurts. “Is i a peak” — yes, which is exactly why the peak problems need template B and a local comparison rather than a global test.
The middle-index overflow is not folklore
It is often told as a museum piece about a bug in the JDK, which undersells it: two problems in this deck have bounds that reach 231 − 1. With lo = 1 and hi = 2147483647, (lo + hi) / 2 evaluates to −1073741824 on any mainstream compiler. In First Bad Version that is a negative version number handed to someone else’s API; in Arranging Coins it is a negative index into a formula. Signed overflow is also undefined behaviour, so the compiler is free to assume it cannot happen and optimise on that basis. Use the subtraction form unconditionally and the question never comes up.
LC 540: the parity alignment is the algorithm
Without if (mid % 2 == 1) --mid; the comparison straddles two different pairs and means nothing. 24,072 failures out of 50,000 valid arrays. This one is worth singling out because the code looks like a normal binary search with a cosmetic adjustment, and the adjustment is the entire insight.
Probing outside the range you were promised
The deck’s First Bad Version starts at version 0 when versions are numbered from 1, and the instrumented mock confirms the probe happens. It passes because the judge’s isBadVersion answers a question it was never asked about. Interactive problems make this failure easy to miss: your bounds are a claim about someone else’s contract, and the grader is usually more forgiving than production.
When the probe is the expensive operation
LC 702 hands you an API instead of an array, and the moment that happens, the cost model changes. Caching a value you already read, or folding an equality test into the main comparison, stops being micro-optimisation. Measured on arrays up to length 20, the version above never needs more than 10 reads, and starting phase two at end / 2 rather than 0 is where a couple of those savings come from.
LC 374 has the same shape in miniature: the deck calls guess(mid) twice per iteration, once to test for zero and once for −1, and caching the verdict halves the oracle traffic. On LeetCode that is free. It stops being free in part two, where LC 1095 caps the API at 100 calls and the array holds 104 elements.
Off-by-one at the empty end
A lower bound is an insertion point, not a match, so it returns a valid index even when the target is absent — and it returns nums.size() when the target exceeds everything. Any code that reads nums[lo] afterwards has to test lo == nums.size() first, and in that order. LC 34 is the problem where this bites, and the payoff for getting the order right is that the empty-array case then needs no guard of its own: lowerBound returns 0, the size test fires, and nothing touches the array.
The same asymmetry is why template A’s two useful exits are worth naming out loud. start is the first true and may be one past the end; end is the last false and may be −1. Whichever you return, ask what it means when the answer does not exist.
How to practise this
Ten problems, two templates, one question. What transfers is small.
- Write both templates from memory, including the exit invariants:
lo == hi + 1for A,lo == hifor B. If you can state those, you never guess at a±1again. - For a new problem, write the predicate as an English sentence before any code, then check whether a larger index could turn a true back into a false.
- Say out loud which side of the boundary you want — first true or last false — and let that pick your return statement.
- Test four inputs by hand every time: one element, two elements, the answer at the far left, the answer at the far right.
- In order: 278 → 35 → 34 → 744 → 74 → 1060 → 540. The first three build the template, 744 and 74 show that the search space is yours to define, and 540 is the one that proves the predicate need not be a value comparison at all.
Next in this series
Every problem above had a sorted array underneath it. The next two posts remove that, one assumption at a time.
- Binary Search Without a Sorted Array: Peaks and Rotations in C++ — seven problems where sortedness is gone and a local comparison or a reference point replaces it. LC 852, 162, 1095, 153, 154, 33, 81.
- Binary Search on the Answer in C++: Five Problems With Nothing to Search — where the search space is the set of possible answers and the input is only how you evaluate the predicate. LC 69, 367, 441, 875, 1011.
Credit and the rest of the series
The problem selection, the ordering, and the framing come from Joseph Choi‘s binary search session deck — including the “two zones” idea that organises all three posts, the missing-count formula for LC 1060, and the parity case analysis for LC 540. The C++ here is my own, rewritten where I preferred different bounds, types, or a different loop shape, and every listing was compiled and differentially tested before publication.
The rest of the pattern series, most closely related first:
- Decrease and Conquer in C++: Twelve LeetCode Problems That Throw the Search Space Away — same instinct, applied where the discarded part is not a clean half.
- Monotonic Stack Pattern in C++: 13 LeetCode Problems, One Rule for Popping — thirteen problems decided by one question: what proves a candidate can never matter again?
- LeetCode Queue Design Patterns in C++: Put the Answer at an Edge — design problems where the work goes into keeping the answer reachable in O(1).
- LeetCode Linked List Patterns in C++: Recovering the Context a Node Doesn’t Have — what to do when a node knows nothing about where it sits.
- Prefix Sum in C++: Nine LeetCode Problems and One Equation — nine problems that collapse into a single subtraction.
- Cycle Sort in C++: Six LeetCode Array Problems That Are the Same Problem — when the values are a permutation of the indices, the array is its own hash table.