Two pointers — every question, written out
Two indices closing in from both ends of a sorted array, eliminating an element against all remaining partners each step. Linear time from sorted order.
Read the two pointers explanation and watch it run
Why is the two-pointer walk O(n) when checking every pair is O(n²)?
Complexity derivation
Each comparison retires one element against every remaining partner, and there are only n elements
Every iteration ends with exactly one pointer moving inward, and the pointers only ever move toward each other, so at most n − 1 iterations can happen. What makes so few comparisons sufficient is that each one is a bulk elimination: an element paired with the best partner still available is refuted against all of them at once. The linear time is a consequence of that proof rather than of clever bookkeeping.
See it run — a[0] has just been retired and left steps to 1 — one comparison, one element gone for good.
The array arrives unsorted. What is the honest total cost of the two-pointer solution?
Complexity derivation
O(n log n) — the walk is linear, but it is dominated by the sort it depends on
Sorting is O(n log n) and the walk is O(n), and sequential phases add, so the sort dominates the pipeline. Quoting "O(n) two pointers" for unsorted input is the single most common overclaim on this pattern. The bound only becomes O(n) when the input is already sorted, which is exactly when the technique is the obvious choice.
What auxiliary space does the walk itself use, and why is that its enduring edge?
Complexity derivation
O(1) — two integer indices, whatever the size of the array
Two integers is the entire state, which is why the pattern stays relevant even where a hash map would be easier to write. On a pre-sorted array it is the only linear-time two-sum that adds no memory at all. That is the axis on which it beats the map, and it is the reason to mention it before the interviewer asks.
The sum is too small, so `left` advances. What has just been proved about the element it leaves behind?
Invariant identification
It cannot reach the target with anyone, since it just failed with the largest partner left
The element was paired with the biggest value still in play and the total still fell short, so every alternative partner is smaller and fails harder. That is one comparison buying up to n eliminations, which is the entire reason the walk is linear rather than quadratic. Prism prints the argument as two lines in the invariants panel before the pointer moves.
See it run — The invariant spells out the generalisation: a[0] is eliminated against every remaining element.
State the loop invariant in a form that still holds for container-with-most-water and palindrome checks.
Invariant identification
Every pair with at least one member outside `[left, right]` has been refuted
Phrasing it about the exterior is what makes the invariant portable: the window only shrinks by adding proofs, so an empty window means every pair has been refuted. Swap the predicate and the same skeleton carries other problems — "this wall can never bound a bigger container", "these two characters matched, so only the interior is undecided". The technique is a settled exterior; the predicate is the part that changes per problem.
See it run — The live window has shrunk to 6..15; every pair touching indices 0–5 is already refuted.
Someone runs the walk on an array that is not actually sorted. What happens?
Edge case reasoning
It returns confident nonsense — including "no such pair" when a pair exists
The elimination argument is a theorem about sorted input: "the largest partner available" only sits at `right` when the array is ordered. Without that, elements retire on evidence that proves nothing, and the walk reports absence it never established. Silent wrong answers are the worst failure mode in the catalogue, so state sortedness as a precondition before writing the loop.
The loop is written `while (left <= right)` instead of `<`. What does that extra iteration allow?
Code diagnosis
It pairs an element with itself, so `a[i] + a[i]` can be reported as a valid pair
When the pointers land on the same index the comparison becomes `a[i] + a[i]`, and a target of twice that value is reported as a pair that does not exist. One character, and the failure only shows on inputs where the target happens to be double an element. Use `<` so the two members of a pair are always two different positions.
On a miss, a candidate moves BOTH pointers "to converge faster". What goes wrong?
Code diagnosis
Untested pairs get skipped, so a real answer can be stepped straight over
Only the pointer whose element has been proven useless may move; the element at the other end has not been refuted against anything. Moving both retires an element that still had untried partners, and the answering pair can be sitting exactly there. It does halve the iterations, which is the tell — the work it skipped was real.
Two-sum with a hash map is also O(n) and needs no sort. So when do you still reach for two pointers?
Comparison
When the input is already sorted and O(1) extra space matters more than keeping indices
The map does one pass, spends O(n) space and hands back original indices; the walk demands sorted input, spends O(1) space and reports positions in sorted order. Neither dominates, so the answer is really a pair of questions: is it already sorted, and do the original indices matter? Saying that out loud is the interview answer — quoting O(n) for both is not.
Suppose the problem insists on the pair’s ORIGINAL indices. What does that do to the plan?
Trade-off & selection
Sort (value, index) pairs and read the stored index — or concede and use the map
Sorting destroys positions, so the index must be carried alongside the value and read back at the end — which keeps the walk but spends O(n) on the pairs. Once the space advantage is gone, the hash map is usually the simpler answer, and noticing that is the point of the follow-up. Two pointers keeps its edge exactly when the input arrives sorted and positions are not part of the answer.
Now return every distinct pair summing to the target, not just the first. What changes?
Edge case reasoning
On a hit, advance both pointers and skip past runs of equal values on each side
A hit refutes both endpoints for each other, so both pointers advance; otherwise a run of equal values on either side regenerates the same value-pair repeatedly. Skipping those runs keeps the walk linear and the output distinct in one move. This is the inner loop of 3Sum, and it is where most 3Sum bugs actually live.
No pair sums to the target. What has the walk established by the time the pointers meet?
Edge case reasoning
Every pair is refuted: each retired element failed against its best possible partner
When the sum is too small the left element has just failed against the largest partner available, so nothing smaller can rescue it — it is refuted against everything at once, and symmetrically on the other side. Meeting pointers therefore mean every pair has been ruled out, after fewer than n comparisons rather than n²/2. The verdict is a proof of absence, which is a stronger thing than "we looked and did not find it".
`a[0] + a[17] = 1 + 18 = 19` against a target of 11. Which pointer moves, and what does the move prove?
Trace prediction
`right` moves in: a[17] just failed with the smallest partner alive, so it can never work
The sum overshoots while a[17] is paired with a[0], the smallest value still in play, so every other partner is at least as large and fails harder. a[17] therefore retires against the entire remaining array, which is a proof rather than a scheduling preference. The trace prints exactly that sentence in the invariants panel before the pointer moves.
See it run — The invariant: a[17] is eliminated against every remaining element, not merely against a[0].
Searching 1..16 for a sum of 23, the right pointer never moves at all. Is the walk still O(n)?
Trace prediction
Yes — the bound counts total pointer movement, and here `left` made all six moves
The linear bound comes from a window that only shrinks, not from symmetry: each iteration moves one pointer one place inward, so at most n − 1 iterations occur however those moves are distributed. On this input every sum stays too small until 7 + 16 reaches 23, so all six moves fall to `left` and `right` sits on index 15 throughout. A run where `right` did all the work would be equally linear.
See it run — Six iterations in: left has reached index 6 while right is still parked on 15.
Opposite-ends and slow/fast pointers share a name. What actually separates them?
Comparison
Opposite ends shrinks a window over sorted data; slow/fast walks one way with a lag
Opposite ends closes a window from both sides and its invariant is "every pair touching the exterior is refuted", which requires order. Slow/fast moves both pointers the same direction at different rates, and its invariant concerns the prefix behind the slow pointer or the gap between them — deduplication, cycle detection, windows. Answering a slow/fast question with an opposite-ends setup is a category error interviewers see weekly.
Container-with-most-water uses the same skeleton on UNSORTED heights. Why is that legitimate?
Trade-off & selection
The eliminated thing changes: the shorter wall can never bound a larger container
The skeleton is "a window whose exterior is settled"; the predicate that settles it is the part that changes per problem. Area is width times the shorter wall, so moving the taller wall inward loses width and cannot gain height — the shorter wall is refuted against every remaining partner, the same shape of proof as before. Sortedness was never the requirement; a valid elimination argument was.
Explain the two-pointer walk to someone who does not code. Say it out loud before revealing.
Explain it plainly
Picture a bookshelf sorted by price, and you want two books that together cost exactly fifty pounds. Put a finger on the cheapest book and a finger on the priciest. This pair costs eight plus forty-seven, which is fifty-five — too much. Now here is the only clever moment in the whole method: that forty-seven pound book was just tried with the cheapest book on the entire shelf, and it still came out too expensive. Every other partner costs more than eight, so the forty-seven can never work with anybody. It is out, permanently, against everyone — so slide the expensive finger inward. If the pair had been too cheap instead, the same argument retires the cheap book, because it had just been tried with the most expensive partner available. One comparison, one book gone for good, so a shelf of a thousand books is settled in about a thousand steps rather than half a million pairings. Where the picture cheats: it works only because the shelf is in price order. On a jumbled shelf "the cheapest book still in play" is not the one your finger is on, every elimination is bogus, and the method will cheerfully announce that no such pair exists while it is sitting right in front of you.
The listener should be able to run the procedure and, more importantly, say why throwing a book away is safe. A strong answer gets to the elimination argument — failed against the best possible partner — and admits that the whole thing collapses if the shelf is not in price order.