Two Pointers

Everything rests on one claim: when you move a pointer, you are not skipping candidates — you are eliminating proven-impossible ones. Here is that claim in full, for the case a[l] + a[r] < target.

1. 1

   The invariant. Every pair (i, j) with i < l or j > r has already been proven not to be the answer. At the start this is vacuously true — nothing is outside the window yet.

2. 2

   The situation. Suppose a[l] + a[r] < target. The partner currently paired with l is the largest value still available.

3. 3

   The consequence of sortedness. For every remaining j <= r we know a[j] <= a[r]. Therefore a[l] + a[j] <= a[l] + a[r] < target.

4. 4

   The discard. So a[l] falls short against every partner that remains. No pair containing l can be the answer. Advancing l deletes that whole row and restores the invariant. The case a[l] + a[r] > target is the mirror image.

Say it in one sentence: if a[l] + a[r] < target then for all j <= r, a[l] + a[j] <= a[l] + a[r] < target, so l participates in no valid pair among the remaining candidates. That sentence is the whole proof — be able to say it out loud, unprompted.

Termination and cost. Every iteration moves exactly one pointer inward, so r - l strictly decreases. The loop runs at most n - 1 times — O(n) after an O(n log n) sort, O(1) extra space.

Why the bound is strict. l < r, not l <= r. At l == r you are looking at one element, not a pair. Use l <= r only when pairing an element with itself is legal in that problem.

a = [1, 2, 5, 9, 12, 14], target = 11. Read the last column as the sentence you would say to an interviewer.

Fifteen pairs existed. You evaluated four. The other eleven were not skipped by luck — step 1 disposed of five at once, step 2 of four, step 3 of three. That is the row/column deletion from the diagram, happening one line at a time.

• The proof is the deliverable, not the code. The loop is six lines and everyone can write it. What separates candidates is being able to justify the move rule without being asked. Volunteer it.
• “Move the side that can only improve” is the entire movement rule, and every later sub-variant is a different answer to the question which side can only improve? In B it becomes a greedy argument about walls; in C it runs inside two fixed loops; in K it stops moving and starts counting.
• Pointers may advance without a comparison. LC 125 skips non-alphanumeric characters inside the loop — the converging skeleton stays identical while the step rule gains a guard. Recognising that the skeleton is invariant is what makes the family feel like one technique instead of eleven.
• Sortedness is the load-bearing assumption, not a convenience. Step 3 of the proof is the only place it is used, and without it the discard is invalid. If a problem is not sorted, either sort it and pay O(n log n), or accept that this pattern does not apply.
• Read the required output type before you reach for a sort. This costs more interviews than any algorithmic error — see the anti-pattern note under LC 1 in the table above.

• ✗Writing while (l <= r) on a pair problem

  Symptom: returns a “pair” made of one element with itself.

  Prevention: ask the question explicitly — is l == r a legal state here? For pairs it is not, so the bound is strict.

• ✗Sorting when the answer needs original indices

  Symptom: correct values, wrong output — the classic wrong answer on LC 1.

  Prevention: before sorting, ask does the output reference positions? If yes, sorting is off the table and you want a hash map.

• ✗Moving both pointers after a miss

  Symptom: intermittently misses valid pairs, and passes small tests.

  Prevention: the proof justifies discarding exactly one end — the one you just tested. The other end was never shown to be impossible, so it stays.

• ✗Expecting it to enumerate all matching pairs

  Symptom: duplicate results once the array contains repeated values.

  Prevention: plain A returns one pair. Enumerating every distinct pair needs the dedup discipline introduced in sub-variant C — do not improvise it here.

Assume h[l] < h[r], so the left wall is the shorter one. We show that no container using l can ever beat the one we just recorded, which makes advancing l lossless.

1. 1

   The objective. area(l, r) = min(h[l], h[r]) * (r - l) — a width factor and a height factor.

2. 2

   The candidates at risk. Discarding l throws away every pair (l, r') with r' < r. Those are the only containers we lose, so those are the only ones we must rule out.

3. 3

   Width strictly shrinks. r' < r, so r' - l < r - l. Every surviving candidate that uses l is narrower.

4. 4

   Height cannot grow. min(h[l], h[r']) <= h[l], and h[l] = min(h[l], h[r]) because h[l] was the shorter wall. So the height factor is capped at exactly the value it already had — whatever h[r'] turns out to be.

5. 5

   Therefore the discard is safe. Smaller width times no-larger height gives area(l, r') < area(l, r), and area(l, r) is already in best. Nothing is lost by advancing l.

Say it in one sentence: moving the taller wall can never increase area, because width shrinks and height is capped by the shorter wall. If you cannot say that out loud, unprompted, you do not have this sub-variant.

Ties are free. When h[l] == h[r] both walls cap the height identically, so either side may be discarded — the code's else branch picks one arbitrarily and stays correct.

Record before you move. best must be updated at the top of the loop body. Discard first and you can throw away the very window that held the maximum.

LC 42 is the same argument one level up. The invariant becomes leftMax = max of h[0..l] and rightMax = max of h[r..n-1], both fully known. The key: the side with the smaller max is fully determined — the other side is guaranteed to have a wall at least as tall, so the water above the current cell depends only on its own side's max. That is why water += leftMax - h[l] is never negative: leftMax was updated to include h[l] on the line above.

h = [1, 7, 3, 6, 4]. Read the last column as the justification you would volunteer to an interviewer before they ask.

Ten containers exist for five bars. You evaluated four, and at no point did you compare a candidate against another candidate — each move was justified on its own, which is exactly what makes the greedy sound.

• This is the sub-variant that decides interviews. In A you move because the sum is too small; in B you move because you can prove the discarded pointer is never in an optimal answer. Different reasoning — and B is where candidates fail, because they write the code correctly but cannot justify it.
• The proof always has the same shape. Every future candidate that still uses this pointer is worse on every factor simultaneously. If you cannot phrase your discard that way, the greedy is probably unsound.
• "Fully determined" is the transferable idea. LC 42's insight — that the side with the smaller maximum can be resolved now, because the other side is guaranteed to hold it up — is reused in dozens of hard problems. It is worth more than the problem it came from.
• Order of operations is load-bearing. Record, then discard. Update the running max, then accumulate. Both LC 11 and LC 42 have a line that is silently wrong if you swap the two statements.
• An O(n squared) instinct passes the samples. Checking all pairs works on small tests and then times out. Recognising that the objective admits a discard proof is the entire difference.

• ✗Discarding the taller wall

  Symptom: quietly wrong maximum — and it passes plenty of small tests.

  Prevention: The proof only licenses dropping the limiting side. Reverse it and you are throwing away candidates you never ruled out.

• ✗Recording the area after moving a pointer

  Symptom: off-by-one maximum; misses the answer exactly when the optimum is the current window.

  Prevention: Compute and store best at the top of the loop body, before any branch.

• ✗In LC 42, accumulating water before updating the max

  Symptom: negative contributions silently subtracting from the total.

  Prevention: leftMax = Math.max(leftMax, h[l]) first, then water += leftMax - h[l] — which is then non-negative by construction.

• ✗Writing while (l <= r)

  Symptom: a zero-width container contributing area 0, or a phantom single-wall answer.

  Prevention: l < r. A container needs two distinct walls, so l == r is meaningless here.

The algorithm is two claims stacked: that fixing an anchor leaves a genuine sub-variant A problem, and that adjacency after sorting makes dedup a constant-time test.

1. 1

   The reduction. Fix a[i]. What remains is find two numbers in a[i+1..n-1] summing to target - a[i] — literally sub-variant A, on a suffix.

2. 2

   The inner converge stays valid. A suffix of a sorted array is still sorted, so A's discard proof carries over unchanged. Nothing about the reduction weakens it.

3. 3

   Sorting solves dedup too. After sorting, equal values sit next to each other. So have I already used this value in this position? becomes a comparison with the immediate neighbour — no set, no extra space.

4. 4

   Both pointers must move on a hit. Advance neither and the loop spins forever. Advance only l and (l+1, r) can re-form the same sum with an equal value, re-recording the triple. l++; r--; is the only safe move.

5. 5

   Dedup must look backward. a[l-1] is the value you just stepped off, so it is guaranteed to exist. a[l+1] may be past the end of the array on the final iteration.

The rule that prevents the single most common 3Sum bug: dedup by comparing to the element you just left (a[l-1], a[r+1]), not the one ahead. Comparing forward reads out of bounds on the last iteration.

The a[i] > 0 prune is target-specific. It is valid for 3Sum because the target is zero and the array is sorted — once the anchor is positive, everything after it is too, so no triple can reach zero. Change the target and the prune changes with it.

4Sum forces long. Four int values near 2^31 overflow silently and produce wrong answers only on adversarial input. Accumulate the sum in long.

3Sum Closest changes the exit, not the movement. There is no equality to return on, so you track a running best and never early-exit. The converge rule itself is untouched — which is the point of learning the family as one skeleton with different step rules.

a = [-1, 0, 1, 2, -1, -4], sorted to [-4, -1, -1, 0, 1, 2], target 0. Watch the highlighted row — that is a dedup site actually firing.

Result: [[-1,-1,2], [-1,0,1]]. Site 1 did visible work here. Sites 2 and 3 stay quiet on this input, but they fire the moment the array holds two copies of a partner rather than of an anchor — for example [-2, 0, 0, 2, 2].

• The dedup discipline is what is actually being tested. 3Sum is the single most-asked two-pointer problem, and everyone can write the converge. The signal is whether all three sites appear, correctly, on the first attempt.
• Name the three sites out loud while coding. Anchor, left partner, right partner. Candidates who narrate them almost never miss one; candidates who treat dedup as a single vague concern usually do.
• Sorting is doing double duty. Validity of the converge and adjacency of duplicates. Saying that unprompted demonstrates you understand why the approach works rather than that you have memorised it.
• The generalisation is recursive. k-Sum is fix one index, solve (k-1)-Sum on the suffix, with the base case being sub-variant A. After 4Sum the whole family is closed.
• Every dedup while needs its own l < r guard. The dedup loops can themselves run the pointers past each other, and the outer condition has already been checked by then.

• ✗Advancing only one pointer after a hit

  Symptom: infinite loop, or the same triplet recorded repeatedly.

  Prevention: After recording, always l++; r--; before the dedup loops run.

• ✗Deduping by looking forward (a[l] == a[l+1])

  Symptom: ArrayIndexOutOfBounds on the last element.

  Prevention: Always dedup against the element you just left: a[l-1], a[r+1].

• ✗Dedup loops missing the l < r guard

  Symptom: pointers cross and you read garbage.

  Prevention: Every inner dedup while re-tests l < r as part of its own condition.

• ✗Summing in int on 4Sum

  Symptom: silent overflow — correct on the samples, wrong on adversarial input.

  Prevention: Accumulate in long. Four values near 2^31 is all it takes.

Compaction looks reckless — you are writing into an array you are still reading. Four lines make it airtight.

1. 1

   The invariant. a[0..w) is the finished, correct output. a[w..rd) is garbage you are free to overwrite. a[rd..n) is untouched input.

2. 2

   Why the write is safe. w <= rd at all times, because rd advances exactly once per iteration while w advances at most once. So the cell at a[w] has already been read on some earlier iteration.

3. 3

   Termination. rd advances on every iteration regardless of which branch is taken, so the loop is O(n) and cannot stall — unlike the converging variants, there is no branch that leaves both pointers where they were.

4. 4

   Why the keep-test reads the output. For keep at most K copies, the real question is have I already written K of these? That is a fact about a[w-K], the output. The input still physically contains the copies you rejected, so a[rd-K] answers a different, wrong question.

The one line that separates LC 26 from LC 80: if (w < K || a[w - K] != v) a[w++] = v; — compare against the output, never the input. The w < K term must come first: it short-circuits the array access while the output is still shorter than K, and Java evaluates left to right.

Once you see this, the whole sub-variant collapses into one line. K = 1 is LC 26, K = 2 is LC 80, and an unconditional predicate with no history at all is LC 27.

The keep-condition may legitimately consult the output. LC 26 tests against a[w-1] — the last value written — rather than against the previous input element. Same principle, K of 1.

LC 283 is this plus a tail. Compact the non-zeros, then fill a[w..n) with zeros. The compaction half is identical.

a = [1, 1, 1, 2, 2, 3], K = 2. Watch row 3: the input has three 1s available, but the output is what gets asked.

Returns w = 5. Row 3 is the whole lesson: three 1s were sitting in the input at that moment, but the test asked the output how many it had accepted. Ask the input instead — a[rd-K] — and this row wrongly writes a third 1.

• State the safety proof, do not just rely on it. The write head never outruns the read head, so I can only ever overwrite something I have already consumed. One sentence, and it retires the interviewer's obvious follow-up.
• The keep-condition may depend on already-written output. LC 26 compares against a[w-1], not against the previous input element. Recognising that the output is a legitimate source of truth is the step from LC 27 to LC 26.
• a[w-K] generalises the whole family. Once the test is expressed against the output at offset K, keep at most k copies is a parameter change rather than a new algorithm.
• The return value is a length, and the tail is deliberately stale. Judges compare only a[0..w). Candidates who try to clean up the tail are usually revealing that they have not internalised what the contract actually is.
• LC 443 composes D with a run-scan. Writing compressed output in place while reading a run is compaction plus sub-variant E's advance rule — a good integration rep once D itself is automatic.

• ✗Comparing against the input instead of the output

  Symptom: wrong on any run longer than K, correct everywhere else — so it passes casual testing.

  Prevention: a[w - K] != v, not a[rd - K] != v. The output knows what you accepted; the input does not.

• ✗Dropping the w < K short-circuit

  Symptom: ArrayIndexOutOfBounds on the first K elements, before the output is long enough.

  Prevention: The guard must be the first operand of the ||. Java short-circuits left to right, which is what keeps a[w-K] from being evaluated.

• ✗Advancing w unconditionally

  Symptom: rejected elements land in the output; the returned prefix is garbage.

  Prevention: rd advances every iteration; w advances only on a keep. That asymmetry is the algorithm.

• ✗Treating the tail beyond w as meaningful

  Symptom: confusion when the array still visibly contains old values after the call.

  Prevention: a[w..n) is defined garbage. Return w and let the caller ignore the rest.

The correctness argument is the same discard logic as sub-variant A, transplanted onto two sequences instead of two ends of one.

1. 1

   The invariant. Both cursors only ever move forward, so the pair (i, j) is the frontier of an as-yet unmatched suffix of each sequence.

2. 2

   The rule. Advance the cursor that cannot possibly participate in a future match.

3. 3

   Why that is safe. Suppose A[i] ends before B[j] begins. It cannot match B[j]. And because B only ever moves forward, everything after B[j] starts even later — so A[i] cannot match any of those either. A[i] is finished, and dropping it discards nothing.

4. 4

   Cost. Every iteration advances at least one cursor and neither ever resets, so the loop runs at most m + n times.

The canonical form of the rule: advance the interval that ends first. Whatever ends first cannot overlap anything that starts later — which is the entire content of LC 986.

lo <= hi, not lo < hi. A single shared point is a legal intersection: [3,3] counts. Using a strict comparison silently drops every touching pair.

LC 392 is the same rule, specialised. The text cursor advances unconditionally; the pattern cursor advances only on a match. Cannot match here means this text character is not the one the pattern needs.

LC 844 runs the skeleton backward with variable-length skips for the backspaces — the nastiest boundary conditions in this sub-variant, and the reason it is starred.

The LC 392 follow-up is a doorway out of the pattern. Once you have many queries against one text, two pointers stops being right: precompute per-character index lists and binary search them. That is Binary Search §M.

A = [[0,2], [5,10]], B = [[1,5], [8,12]]. Row 2 is why the emit test is <= and not <.

Three iterations for four intervals. Notice that no cursor was ever compared against anything it had already passed — that is monotonicity doing the work, and it is why this is O(m + n) rather than O(m * n).

• This is the merge step, generalised. Saying so out loud immediately explains the cost and the shape of the loop, and it tells the interviewer you see the family rather than the instance.
• Only the step rule changes between problems. The skeleton — two cursors, a while on both bounds, advance the loser — is identical in LC 392, 986 and 844. Recognising the invariant part is what makes the sub-variant transferable.
• State the cost argument as a sentence. Each iteration advances at least one cursor and neither ever resets, so the work is bounded by m + n. That is more convincing than asserting O(m + n).
• The inclusive bound is a real interview trap. lo <= hi on the emit test. Touching intervals are the test case that separates a correct solution from one that looks correct.
• Backward is still forward. LC 844 walks from the ends inward, but each cursor is still monotone in its own direction, so the same argument applies unchanged.

• ✗Emitting with lo < hi instead of lo <= hi

  Symptom: every single-point intersection is silently dropped.

  Prevention: [3,3] is a valid intersection. The bound is inclusive.

• ✗Advancing both cursors after a match

  Symptom: valid pairs get skipped when one interval overlaps several on the other side.

  Prevention: Advance only the one you proved is finished. In LC 986 a long interval must stay put while several short ones pass it.

• ✗Advancing the cursor that ends later

  Symptom: misses overlaps, and the error is not obvious on small inputs.

  Prevention: Drop whoever ends first — that is the one with no possible future partner.

• ✗Resetting a cursor to re-scan

  Symptom: quietly degrades to O(m * n) and passes every correctness test.

  Prevention: Neither cursor may move backward. If the problem seems to demand it, you need a different tool.

One inequality carries the whole sub-variant. Everything else is bookkeeping around it.

1. 1

   The invariant. w >= i and w >= j at all times, so the write head never lands on unread input.

2. 2

   Why w >= i holds. w starts at m + n - 1 and i at m - 1, a gap of n. Each iteration decrements w by exactly one and at most one of i or j. So w falls no faster than i, and the gap never closes.

3. 3

   Why the loop tests j only. If j runs out, whatever remains in a[0..i] is already sorted and already sitting in its final position. There is literally nothing to do, so the loop should stop.

4. 4

   Why the i >= 0 guard is inside the ternary. If i runs out first, the remaining elements of b still need copying. The guard makes the ternary fall through to b[j--] and drains b correctly.

The rule worth generalising past this problem: write from the tail whenever destination and source overlap. LC 88 is the smallest instance of a move you will reuse for in-place shifts and any resize-in-place.

The asymmetric loop condition surprises people. Looping on j alone looks like a bug until you say the reason out loud: leftover a values are already home; leftover b values are not.

Guard order matters. (i >= 0 && a[i] > b[j]) — Java short-circuits left to right, so the bounds check must come first or the comparison reads a[-1].

a = [1, 3, 5, _, _, _] with m = 3, b = [2, 4, 6] with n = 3. Watch w stay strictly ahead of i in every single row.

j hits -1, the loop exits, and a[0] = 1 was never touched — it was already in its final position, which is exactly what step 3 of the proof predicted. Note row 2: a[4] was written with the value read from a[2], and a[2] was not needed again until row 4 had already consumed it.

• Name the failure before you name the fix. Forward merge clobbers a[i] before I read it. Stating the bug first makes the backward choice sound derived rather than memorised.
• The invariant is a single inequality. w >= i. If you can produce that and its one-line justification, the rest of the code writes itself.
• The loop condition is the interesting line. Looping on j only is the part interviewers probe. Have the reason ready: leftover a is already in place.
• This generalises well beyond merging. Destination overlaps source, so write from the end is the transferable sentence — it applies any time you compact or expand an array in place.

• ✗Merging forward into the shared array

  Symptom: the first write destroys a[0], and the output is scrambled in a way that still looks plausible on sorted-ish input.

  Prevention: Write backward whenever the destination and source overlap.

• ✗Looping on i instead of j

  Symptom: leftover b values never get copied, so the head of the array keeps stale zeros.

  Prevention: Loop on j. Leftover a is already home; leftover b is not.

• ✗Dropping the i >= 0 guard

  Symptom: ArrayIndexOutOfBounds as soon as a is exhausted before b.

  Prevention: Keep the guard first inside the ternary — Java short-circuits left to right.

Detection is easy to believe: a faster runner on a loop must eventually collide with a slower one. The entry point is the part worth deriving, and you should be able to do it on a blank page rather than recalling the reset step.

1. 1

   Name the three distances. a = head to entry, b = entry to the meeting point, c = cycle length.

2. 2

   Write down what each pointer travelled. At the meeting, slow has travelled a + b. fast has travelled 2(a + b) because it moves twice as fast — and it has also travelled a + b + kc, having gone round the loop k times.

3. 3

   Equate the two expressions for fast. 2(a+b) = a+b+kc, so a + b = kc, so a = kc - b.

4. 4

   Read what that means. Walking a steps from the head, and a steps onward from the meeting point, lands on the same node — the entry. So reset one pointer to the head and advance both one step at a time until they agree.

Derive this, never memorise it: 2(a+b) = a+b+kc gives a+b = kc gives a = kc - b, so walking a steps from head and a steps from the meeting point lands on the same node.

Hop first, compare second. Both pointers start at the head, so testing slow == fast before the first move reports a cycle on every input, including a single node.

Both guards, in that order. fast != null && fast.next != null — the second dereference is only safe because Java short-circuits left to right. Drop either and even-length acyclic lists throw.

LC 876 has a deliberate ambiguity. Which middle you land on for even-length lists depends on the loop condition; decide which one the problem wants before you write it.

LC 287 rewrites the pointers as values. slow = a[0], fast = a[a[0]], and the step becomes slow = a[slow]. Same algorithm, no nodes.

1 -> 2 -> 3 -> 4 -> 5 -> 3 (the tail links back to node 3). So a = 2, the entry is node 3, and the cycle 3 -> 4 -> 5 has length c = 3.

Phase two took exactly a = 2 steps, which is what the derivation promised. If you can produce that promise before you write phase two, you are deriving the algorithm rather than recalling it.

• Derive the entry formula, do not recall it. The mastery gate for this sub-variant is specifically derive a = kc - b on a blank page. Interviewers ask why the reset works far more often than they ask for the code.
• LC 287 is the point of the whole sub-variant. Applying Floyd to i -> a[i] without being told it is a linked-list problem is the transfer. The signal it sends is that you see cycle detection as a property of functional graphs, not of a data structure.
• Speed ratio and fixed gap are different tools. Ratio answers is there a loop; gap answers how far from the end. Conflating them produces confident, wrong code.
• The dummy head is not decoration. It removes the special case where the node to delete is the head itself. Reaching for it unprompted is a small, strong signal about linked-list fluency.
• Composition problems are cheap once G is solid. LC 143 and LC 234 are both find middle, reverse, merge. Pick one as an integration rep; doing both teaches nothing extra.

• ✗Comparing slow == fast before the first hop

  Symptom: reports a cycle immediately on every input — both pointers start at the head.

  Prevention: Hop first, compare second. The check belongs after the two moves, not before.

• ✗Guarding with only fast != null

  Symptom: NullPointerException on even-length acyclic lists, when fast.next is null but fast is not.

  Prevention: Both guards, in order: fast != null && fast.next != null.

• ✗Memorising the reset step without the derivation

  Symptom: you produce the right code and then cannot answer why does that work?, which is the actual question.

  Prevention: Derive a = kc - b from 2(a+b) = a+b+kc every time until it is automatic.

• ✗Using a speed ratio where a fixed gap is wanted

  Symptom: off-by-one on n-th from the end, or a midpoint that is one node off.

  Prevention: Positional questions want a gap; cycle questions want a ratio.

The mid++ on one swap and not the other is the entire problem. It is not arbitrary — it falls straight out of the region invariants.

1. 1

   The four regions. [0, lo) are zeros, [lo, mid) are ones, [mid, hi] is unknown, (hi, n) are twos. Note the unknown region is closed on both sides.

2. 2

   The low swap advances mid. When a[mid] == 0 you swap it with a[lo]. The value swapped back into mid came from [lo, mid) — the region you have already classified as ones. So it is a 1, it is already in the right region, and mid may safely advance.

3. 3

   The high swap does not advance mid. When a[mid] == 2 you swap it with a[hi]. The value swapped back came from [mid, hi] — the unknown region. Nobody has looked at it. Advancing mid would leave it forever unclassified.

4. 4

   The loop bound follows. Because the unknown region is closed, mid == hi still contains one unexamined element. The condition must be mid <= hi.

The asymmetry is the entire problem: mid++ on the low swap, no mid++ on the high swap. Derive it from where the incoming value came from — do not memorise it.

Quickselect reuses the primitive as a search. Partition, look at where the pivot landed, and recurse into only the side containing k. Discarding one side each time gives expected O(n) rather than the O(n log n) of a full sort.

LC 905 is the degenerate two-way case and teaches nothing new once three-way is solid — which is exactly why the table marks it optional.

Watch rows 1 and 4. Both are high swaps, and in both mid deliberately stays where it is.

Row 1 is the whole lesson. Had mid advanced there, the 0 swapped in from the unknown region would never have been examined, and it would have been left sitting in the ones region — a silent, plausible-looking wrong answer.

• Derive the asymmetry out loud. Low swap pulls from a classified region, high swap pulls from the unknown region. That one sentence is what the mastery gate asks for, and it is the difference between understanding DNF and having memorised it.
• The closed unknown region forces mid <= hi. Half-open versus closed regions is the recurring source of off-by-one bugs across this entire document. Write the region bounds down before writing the loop.
• Partitioning is a search primitive, not just a sort step. That reframing is what makes quickselect obvious rather than clever: you are binary searching over positions, using a partition as the test.
• Partitioning is not stable. If the problem cares about relative order inside a class, this pattern is wrong. Worth saying before you are asked.
• Quickselect's O(n) is expected, not worst case. Adversarial pivots give O(n^2). Naming that unprompted, along with random pivot selection as the mitigation, is a strong signal.

• ✗Advancing mid after the high swap

  Symptom: unsorted output, silently — and small inputs often still come out right.

  Prevention: Trace where the swapped-in value came from. The high swap pulls from the unknown region, so it must be classified next iteration.

• ✗Writing mid < hi instead of mid <= hi

  Symptom: the last element is never classified.

  Prevention: The unknown region is closed: [mid, hi]. At mid == hi there is still work to do.

• ✗Advancing lo without advancing mid on the low swap

  Symptom: the ones region gets corrupted and elements are re-examined.

  Prevention: Both move together on a low swap: swap(a, lo++, mid++).

• ✗Assuming quickselect must fully sort a side

  Symptom: you rebuild O(n log n) and lose the entire advantage.

  Prevention: Recurse into only the side containing k. Discarding the other half is where the speed comes from.

The expansion loop is trivially correct. The bug surface is entirely in what the loop leaves behind when it stops.

1. 1

   The invariant. Inside the expand loop, s[l..r] is a palindrome. That is what the loop maintains and it is true at every check.

2. 2

   The growth rule. If s[l-1] == s[r+1], then wrapping those two characters around a palindrome yields a longer palindrome. So push both pointers outward.

3. 3

   The exit condition overshoots. The loop stops the moment the test fails — but it has already decremented l and incremented r. So at exit, s[l..r] is not the palindrome; it is one character too wide on each side.

4. 4

   The correction. The real palindrome is [l+1, r-1], and its length is (r-1) - (l+1) + 1 = r - l - 1. Both the bounds and the length formula come from the same off-by-one.

The correction everybody gets wrong exactly once: the loop exits one step too far on each side, so the palindrome is [l+1, r-1] and its length is r - l - 1 — not r - l + 1.

LC 647 counts instead of maximising. Every successful expansion corresponds to exactly one distinct palindromic substring, so the body becomes count++ and no correction is needed at all — you are counting iterations, not measuring a final window.

The out-of-bounds guards double as the exit. l >= 0 && r < s.length() sits in the same condition as the character comparison, so running off either end simply ends the expansion. No separate boundary case is required.

Cost is O(n^2) worst case — for example "aaaa...", where every centre expands the full width. That is expected and acceptable here; O(n) requires Manacher's, which is almost never the point of the question.

Two calls, showing the successful odd centre and an even centre that dies immediately. Watch the final row of each: the returned bounds are not the loop's exit bounds.

Row 3 is the correction doing real work: the loop exited at l = -1, r = 3, which is not even a valid range. Row 5 shows the same formula degrading gracefully to length zero when the centre fails on the first test — no special case needed.

• State the correction before you write the loop. [l+1, r-1], length r - l - 1. Writing it down first stops you from deriving it under pressure, which is when the sign errors happen.
• Both parities, always. expand(c, c) and expand(c, c+1) on every index. A solution that handles only odd centres fails on "aa" — one of the first tests any interviewer reaches for.
• This is mechanically a two-pointer, taught elsewhere as a string or DP problem. Recognising it as the same family — an invariant maintained over a growing region — is exactly the kind of connection the pattern breakdown is built to surface.
• Counting and maximising need different bookkeeping. LC 5 needs the corrected bounds; LC 647 needs only a counter incremented per successful expansion. Same skeleton, different read-off.
• Know that Manacher's exists, and that it is not the answer here. Naming the O(n) algorithm and then explaining why O(n^2) is appropriate for the constraints reads as judgement. Reaching for Manacher's unprompted usually does not.

• ✗Using [l, r] after the loop

  Symptom: off-by-two on every answer — the returned substring is always two characters too long.

  Prevention: The loop overshoots by one on each side. Use [l+1, r-1], length r - l - 1.

• ✗Only expanding odd centres

  Symptom: fails on any even-length palindrome, starting with "aa".

  Prevention: Two calls per index: expand(c, c) and expand(c, c+1).

• ✗Computing length as r - l + 1

  Symptom: consistently two too large, which then corrupts the best-so-far comparison.

  Prevention: After the overshoot the length is r - l - 1. Derive it from (r-1) - (l+1) + 1.

• ✗Checking bounds outside the loop condition

  Symptom: either an out-of-bounds read or a clumsy special case for the string's ends.

  Prevention: Put l >= 0 && r < s.length() in the same condition as the character test.

Cyclic sort is one of the few patterns here where the loop terminating at all is the non-obvious claim, and where a plausible-looking guard causes an infinite loop.

1. 1

   The invariant. Once a[i] == i + 1, index i is permanently correct and is never disturbed again.

2. 2

   Termination. Every swap places at least one value in its final home. There are n homes, so there are at most n swaps in total across the entire run — the algorithm is O(n) despite the nested while.

3. 3

   Why you must compare values. With duplicates, two equal values want the same home. The index test i != correct stays true forever and the loop spins. The value test a[i] != a[correct] sees that the home is already occupied by the right value and moves on.

4. 4

   Why the range guard must come first. correct = a[i] - 1 is only a legal index when a[i] is in [1..n]. The guard a[i] >= 1 && a[i] <= n must be evaluated before a[correct] is touched — short-circuit order is doing real work here, not just tidiness.

The two guards that make it both safe and finite: a[i] >= 1 && a[i] <= n && a[i] != a[correct] — range first so the index is legal, and compare values, never indices.

The verification pass is the actual answer. The swap phase only arranges; it does not report. Scan for the first k with a[k] != k + 1 and return k + 1; if every slot is correct, the answer is n + 1.

Same machine, different read-off. LC 448 collects all indices that fail the check; LC 41 returns only the first. The arrangement phase is identical.

LC 442 is the sign-marking cousin. Instead of moving values, negate a[|v|-1] to record seen. Same index-as-hash idea, different encoding — worth knowing that both exist.

n = 4. Note how i refuses to advance while a swap is still productive, and how the out-of-range value at index 0 is simply stepped over.

Four swaps for four elements, exactly as the termination argument predicts. Rows 3 and 4 are a chain — one swap enabling the next at the same index — which is precisely the case that makes the linear bound look doubtful until you count placements rather than iterations.

• Count placements, not iterations, when you argue the cost. Each swap puts at least one value permanently home, and there are only n homes. That single sentence answers the obvious objection to the nested loop.
• The value-versus-index comparison is the whole trap. a[i] != a[correct], never i != correct. Duplicates make the index form spin forever, and the difference is invisible on duplicate-free test data.
• Short-circuit order is load-bearing, not stylistic. The range guard protects the array access that follows it in the same expression. Reordering the conditions turns correct code into an exception.
• Two phases, and the second is where the answer lives. Candidates who stop after the swap loop have arranged the data and answered nothing.
• LC 41 is the hardest gate in this pattern. It needs the range guard, the value guard and the verification pass all correct simultaneously. The table is explicit that solving it closes the sub-variant.

• ✗Comparing indices: i != correct

  Symptom: infinite loop the moment the input contains a duplicate.

  Prevention: Compare values: a[i] != a[correct]. The home is satisfied when it holds the right value, regardless of which copy got there.

• ✗Omitting the range guard

  Symptom: ArrayIndexOutOfBounds on negatives or on values larger than n.

  Prevention: Guard a[i] >= 1 && a[i] <= n first — short-circuit order is what protects the index.

• ✗Advancing i after a swap

  Symptom: values get stranded, because the value you just swapped in has not been examined.

  Prevention: i advances only when no productive swap is available: out of range, or already home.

• ✗Skipping the verification pass

  Symptom: the array ends up arranged but the function returns nothing meaningful.

  Prevention: Scan for the first k where a[k] != k + 1, return k + 1, and return n + 1 if the scan completes.

The batch is not an optimisation bolted on afterwards — it is a direct consequence of sortedness, in the same way the discard was in sub-variant A.

1. 1

   Fix the largest side. The outer loop pins a[k] as the longest side. For a valid triangle you need a[l] + a[r] > a[k] with l < r < k — and because the array is sorted, the other two triangle inequalities hold automatically. One test instead of three.

2. 2

   The success case batches. If a[l] + a[r] > a[k], then for every l' in [l, r-1] we have a[l'] >= a[l], so a[l'] + a[r] > a[k] as well. All of those pairs are valid, right now, without checking them.

3. 3

   Count them and retire r. That block is (r-1) - l + 1 = r - l pairs. Add them, then r--: a[r] has been fully accounted for as a partner within this window.

4. 4

   The failure case is A's discard. If a[l] + a[r] <= a[k], then a[l] is too small with every partner up to a[r], so l++. That is exactly sub-variant A's rule, unchanged.

The transferable line: count += r - l instead of count++. The same trick reappears verbatim in sliding-window counting (§2.F) — which is why this sub-variant closes the pattern.

r - l versus r - l + 1 is the whole K-to-done gate. Here the pairs are (l, r), (l+1, r), ..., (r-1, r) — the partner r itself is excluded because the problem requires l < r. In LC 713 the window [l, r] is a subarray whose right endpoint counts as a member, giving r - l + 1. Same batching idea, different membership rule.

Know which quantity you are counting before you write the +=. Pairs inside a window, or windows ending at r? Getting that wrong produces an answer that is off by exactly the number of iterations, which is maddening to debug.

Sorted already. The outer loop walks k down from the largest side; the inner converge does the counting.

Answer 3, and the triangles are (2,2,3), (2,3,4) and (2,3,4) using the other 2. Row 1 banked two triangles from a single comparison — had you written count++ there, you would have returned 2 and the bug would look like an off-by-one rather than a missing batch.

• Fixing the largest side is the setup that makes it work. It reduces three triangle inequalities to one test. Fixing the smallest side instead leaves you checking all three and the converge no longer applies.
• count += r - l is the sentence to remember. The mastery gate asks you to explain why it is correct and to connect it to count += r - l + 1 in LC 713. Having the code without that connection is having the problem, not the pattern.
• The batch follows from sortedness, not from cleverness. Everything to the left of a working l also works, because it is at least as large. Same shape of argument as A's discard proof, used to count rather than to eliminate.
• This is the bridge out of the pattern. The identical at-most batching drives sliding-window counting in §2.F. Recognising it there for free is the payoff for learning it here.
• Counting problems rarely want the members. If you find yourself materialising the pairs to count them, you have already lost the complexity argument.

• ✗Writing count++ instead of count += r - l

  Symptom: undercounts badly, and the result still looks like a plausible near-miss.

  Prevention: One successful comparison certifies an entire block of partners. Count the block.

• ✗Using r - l + 1 for pair counting

  Symptom: overcounts by exactly one per successful step — it counts (r, r), which is not a pair.

  Prevention: Pairs need l < r, so the partner r itself is excluded: r - l. The +1 form belongs to subarray counting like LC 713.

• ✗Fixing the smallest side in the outer loop

  Symptom: you now need all three triangle inequalities and the converge no longer justifies a discard.

  Prevention: Fix the largest side. Sortedness then makes the other two inequalities free.

• ✗Moving l after a successful batch

  Symptom: double-counts pairs that the batch already covered.

  Prevention: After banking r - l, retire the right pointer: r--. a[r] is finished as a partner in this window.