3Sum (LeetCode #15)

3Sum asks for every unique triple of values in an array that sums to zero. The standard solution sorts the array, fixes one element as an anchor, and runs a two-pointer sweep over the rest — O(n²) instead of the O(n³) of testing every triple, with duplicates removed by adjacency checks instead of a hash set.

Sorting pays twice. It costs O(n log n) up front, and in return it makes the converging-pointer rule valid (the smallest candidate is always on the left, the largest on the right) and parks equal values next to each other — so every duplicate check, at the anchor and at both pointers, is one comparison against a neighbor.

How 3Sum works

Fix the smallest element of a candidate triple as the anchor nums[i]. The other two values must cancel it, so the problem shrinks: find a pair in the sorted suffix that sums to need = -nums[i]. That is exactly the two-pointer search from the Two Pointers lesson, run once per anchor. lo starts just right of the anchor, hi at the far end; a pair sum below need advances lo (the left value is too small for any partner), a sum above need retreats hi, and a hit records the triple [nums[i], nums[lo], nums[hi]].

Three details carry the rest of the algorithm, and all three lean on sortedness:

• Equal anchors are skipped. If nums[i] == nums[i - 1], the previous anchor already swept a larger suffix for the same need — this anchor can only rebuild triples that are already recorded. Sorting made the duplicate adjacent, so detecting it is one comparison against the left neighbor.
• After a match, both pointers move, then slide past duplicates. A recorded triple uses both ends. Keeping hi and advancing only lo could only re-match if the next nums[lo] equals the one just used — a duplicate triple by definition. So both ends move, and two small while-loops slide lo and hi past any run of equal values before the next test.
• A positive anchor ends everything. Once nums[i] > 0, the anchor is the smallest value in every remaining triple, so every remaining sum is positive. break, not continue — the sort ordered the anchors, so the first positive one proves there is nothing left to find.

3Sum step by step

The default animation uses nums = [-1, 0, 1, 2, -1, -4].

1. Sort. The cells reorder to [-4, -1, -1, 0, 1, 2]. Watch the two -1s land side by side — that adjacency is what the skip checks rely on later.
2. Anchor -4 (index 0), need = 4. lo and hi frame the suffix. The sweep tests -1 + 2 = 1, then -1 + 2 = 1, 0 + 2 = 2, 1 + 2 = 3 — every sum is below 4, so lo walks all the way across and the pointers meet. An anchor can fail; nothing is recorded.
3. Anchor -1 (index 1), need = 1. First test: -1 + 2 = 1 — a hit. [-1, -1, 2] lands in the results panel. Both pointers move inward; the new neighbors (0 and 1) are not duplicates, so no skip fires.
4. Same anchor, next pair. 0 + 1 = 1 — a second hit under the same anchor. [-1, 0, 1] is recorded, both pointers move, and they cross. One anchor can yield several triples.
5. Anchor candidate -1 (index 2) is skipped. It equals its left neighbor — the sweep it would run is a subset of the one that just finished. This one beat is the whole duplicate-prevention argument.
6. Anchor 0 (index 3), need = 0. The only pair left tests 1 + 2 = 3 > 0, so hi retreats and the pointers meet. The loop stops here — anchors past n - 3 cannot start a triple.
7. Done. The panel holds [[-1, -1, 2], [-1, 0, 1]] — every zero-sum triple, each exactly once.

On the canvas, the purple anchor cell and the need readout in the header are the reduction made visible: each anchor turns 3Sum into one 2Sum sweep, drawn with the same bracket and pointer grammar as the Two Pointers lesson. Cells the sweep has ruled out fade; cells before the anchor stay dim as retired history; the tests counter in the header climbs by one per pair check — n anchors times at most n tests is the O(n²) you can watch.

One thing this input never shows: the two pointer-side skips after a match (its post-match neighbors happen not to repeat). Flip Config → Scenarios → "Duplicates everywhere" to watch lo and hi slide past equal runs — without those two loops, the very next test would record the same triple again.

Time and space complexity

The sort's O(n log n) is absorbed by the O(n²) sweep total: each of the n anchors runs at most one O(n) converging sweep. Extra space is constant beyond the output list and the sort's own workspace — the O(1) claim is about the algorithm layer, and a library sort like Python's Timsort can use up to O(n) scratch internally. The input editor is capped at 8 values from −20 to 20 so every beat stays legible; that is a display limit, not an algorithmic one.

The pattern transfers. Any target works, not just zero: need = target - nums[i], and the early exit becomes 3 * nums[i] > target — the anchor is the smallest of the three values, so the triple sums to at least 3 * nums[i]. Keeping nums[i] > 0 would stop [1, 2, 3] with target 6 at the first anchor and miss the answer. And k-sum peels anchors the same way — fix one element, recurse on (k−1)-sum, until 2Sum-on-sorted finishes the job in linear time. Reach for this shape when you want unique value triples and sorting is allowed; note that nums.sort() reorders the caller's array in place, so pass a copy when the original order matters elsewhere.

Edge cases

• Exactly three values give a single candidate triple: one one-test sweep, unless the first value is positive and the break fires before any test.
• All values positive ends on the very first anchor via the nums[i] > 0 break, with an empty result.
• All values negative also yields nothing, but differently: no anchor is positive, so the break never fires — every sweep just runs out with sums below need. Same answer, different exit.
• All zeros is the dedup stress test: [0, 0, 0, 0, 0] has ten index combinations but exactly one unique triple, [0, 0, 0].
• No solution is a valid outcome, not an error — each sweep ends when the pointers meet without a match (or the positive-anchor break ends the search early), and the function returns an empty list.
• Duplicates straddling a match, as in [-2, 0, 0, 1, 2, 2]: both post-match skips fire, keeping [-2, 0, 2] from being recorded twice.

Common mistakes

• Skipping the anchor check. Without nums[i] == nums[i - 1] → continue, the second -1 in the default input re-finds [-1, 0, 1] and the output gains duplicates.
• Moving one pointer after a match. Advancing only lo re-tests pairs that can only succeed as duplicates; the correct move is both ends, then the duplicate slides.
• Deduping with a set of triples instead of adjacency. It works, but it spends O(k) memory and hashing to solve a problem the sort already solved — the adjacency skips also hand you sorted, normalized output for free.
• Sorting the caller's array. nums.sort() mutates the input in place; if the caller needs the original order, sort a copy.
• Writing continue instead of break for a positive anchor. Both are correct, but continue keeps scanning anchors that provably cannot work; break uses the sorted order as a proof and stops.
• Comparing the pair sum to 0 instead of need. Also correct if the anchor is added into the sum, but mixing the two conventions mid-implementation — summing two values yet comparing against 0 — silently breaks correctness: with a nonzero anchor it misses valid triples and can record ones that do not sum to 0.