---
title: "3Sum (LeetCode #15)"
description: "Sort, fix one number, walk two pointers inward — skipping duplicates"
source: https://vizlearn.app/algorithms/leetcode/three-sum
---

# 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](https://vizlearn.app/algorithms/search/two-pointers), 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 `-1`s 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

| Approach                        |       Time | Extra space | Duplicate handling                  |
| ------------------------------- | ---------: | ----------: | ----------------------------------- |
| Brute force — test every triple |      O(n³) |        O(1) | Needs a set of normalized triples   |
| Sort + anchor + two pointers    |      O(n²) |        O(1) | Adjacency skips, no extra structure |

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.