Fix one, two-pointer the rest

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

From −1, 0, 1, 2, −1, −4, find every set of three numbers that adds to 0, without listing the same set twice. The answers are (−1, −1, 2) and (−1, 0, 1). By hand you would try triples: six numbers make 20 triples, and for n numbers about n³ ÷ 6. A thousand numbers is 166 million triples, and you would still have to weed out duplicates like (−1, 0, 1) found twice from the two −1s.

Two-sum on a sorted list is cheap (two pointers, O(n)). The question is how to turn three-sum into many two-sums without paying too much.

Build the structure, one piece at a time

Piece one: sort. −4, −1, −1, 0, 1, 2. Sorting is what makes both the two-pointer walk and the duplicate skipping possible.

Piece two: pin the first number. Walk an index i from left to right; for each one, the remaining job is "find two numbers in positions after i that add to −nums[i]". That is exactly the sorted two-sum, so run the converging two pointers l = i + 1 and r = last on the suffix.

Piece three: skip duplicates at every level. If nums[i] equals nums[i − 1], every triple starting here was already found from the previous i, so skip. Likewise after recording a triple, step l past repeated values and r past repeated values.

You can stop early once nums[i] > 0: with a sorted list, three positives cannot sum to zero.

Why it is correct

Two invariants. The outer one: when the pin is at i, every triple whose smallest index is less than i has already been reported. The inner one is the two-sum invariant: the pair, if it exists in the suffix, lies within [l, r]. Together they mean every zero-sum triple is found when its smallest index is pinned.

Why no duplicates? A set of three values, in sorted order, is (a, b, c). It is reported only when the pin sits on the first occurrence of a (later equal pins are skipped) and the pointers sit on the first b and last c they meet; after reporting, both pointers jump past equal values, so the same (b, c) is not seen again for this pin. Each value-set is therefore reported exactly once.

Why it is fast

Sorting costs O(n log n). Each pin runs one two-pointer walk over at most n elements, O(n), and there are n pins:

n log n + n · n = O(n²)

For a thousand numbers that is about a million steps instead of 166 million triples. The pattern generalises: k-sum is k − 2 nested pins around one two-pointer walk, O(n^{k − 1}).

How to recognise it in an interview

Cues: "three (or four) numbers that sum to", "closest to a target", "count triples with …", and the word "unique" or "no duplicate triples". Say: "Sort, fix the first element, and solve the rest as a two-pointer two-sum on the suffix, skipping duplicates at each level."

3Sum is the example. 3Sum Closest keeps the best |sum − target| seen during the walk instead of stopping at equality. Valid Triangle Number pins the largest side and counts how many pairs in the prefix satisfy a + b > c, where a "too small" sum lets you move l and a valid one lets you count r − l pairs at once.

02The idea in one line

Sort, pin index i, solve a 2-sum on the suffix; skip duplicates.

Reach for it when: k-sum problems, count triangles, closest triple.

Cost: O(n²) time.

03The walk-through, step by step

The video works one example: 3Sum on [-1,0,1,2,-1,-4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort, pin index i, then two-pointer the suffix for −nums[i]
2. Pin -4: need two numbers summing to 4
3. -4 + -1 + 2 = -3 < 0: move l right
4. -4 + -1 + 2 = -3 < 0: move l right
5. -4 + 0 + 2 = -2 < 0: move l right
6. -4 + 1 + 2 = -1 < 0: move l right
7. Pin -1: need two numbers summing to 1
8. -1 + -1 + 2 = 0: triple [-1, -1, 2]
9. -1 + 0 + 1 = 0: triple [-1, 0, 1]
10. Triples: [−1,−1,2] and [−1,0,1]; later pins are ≥ 0, no more sums to 0
11. n pins × linear two-pointer sweep: O(n²)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Two Pointers: Opposite ends converge, Reader / writer pointers, Dutch national flag partition, Merge two sorted sequences, Two-sided max walls.