3Sum: Sort First, Then Let Two Pointers Do the Work
The sorted two-pointer solution to 3Sum explained step by step — sorting, duplicate skipping, JavaScript code, a worked walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
3Sum is where pair-sum problems grow up. Two Sum hands you a target and asks for one pair; 3Sum asks for every unique triplet that sums to zero — duplicate values in the input, no duplicate triplets in the output, three moving parts instead of two. It filters out anyone who memorized Two Sum without understanding it.
The winning move is a reframe: sort the array, lock one number in place as an anchor, and the leftover problem is exactly Two Sum on a sorted array — solvable with two inward-walking pointers in linear time. One borrowed idea turns an O(n³) grind into a clean O(n²). If you'd rather watch the pointers move than read about them, step through it interactively.
The problem
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that the three indices are distinct and the three values sum to 0. The answer must not contain duplicate triplets.
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]Two details in that statement drive the whole solution:
- The answer wants values, not indices — so sorting the array is allowed, and sorting is what unlocks everything.
- Unique triplets only —
[-1, -1, 2]counts once even though two different-1s exist. Duplicate handling isn't an edge case here; it's half the problem.
The brute force baseline
Three nested loops, check every combination:
function threeSum(nums) {
const result = [];
const seen = new Set();
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = triplet.join(",");
if (!seen.has(key)) {
seen.add(key);
result.push(triplet);
}
}
}
}
}
return result;
}That's O(n³) comparisons — on a 3,000-element array, roughly 4.5 billion triple-checks. Worse, it doesn't even handle deduplication cleanly: you're forced to bolt on a set of stringified triplets, paying extra time and memory to throw away work you shouldn't have done at all.
The key insight: fix one, two-point the rest
This is the sorted two-pointer pattern. Sort the array once, then walk an anchor i across it. For each anchor, the question collapses to: find two numbers in the rest of the array that sum to -nums[i]. That's Two Sum on a sorted range — and Two Sum II already showed how to answer it in O(n) with zero extra space.
Why does sorting make the pair search linear? Because sorted order gives the pointers directional control: put left just after the anchor and right at the end. If the three-way sum is too small, only moving left rightward can increase it; if too big, only moving right leftward can decrease it. Every comparison eliminates one candidate for good — each anchor's scan is a single linear pass.
Sorting buys a second win for free: duplicates become adjacent, so skipping a repeated value is a one-line neighbor comparison instead of hashing whole triplets. One sort, two problems solved.
The optimal solution
This is the exact algorithm the 3Sum visualizer traces line by line:
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}Three lines deserve a second look:
if (i > 0 && nums[i] === nums[i - 1]) continue;— if this anchor equals the previous one, every pair it could form was already explored last iteration. Reprocessing it can only produce repeat triplets.- The two inner
whileskips after a match — both pointers hop over any run of equal values before stepping inward. Without this,[-2, 0, 0, 2, 2]would emit[-2, 0, 2]twice. left++; right--;after a match — both pointers must move. With the anchor fixed, keeping either pointer in place cannot produce a new valid pair; keeping both produces an infinite loop.
One optional micro-optimization: once nums[i] > 0, everything to the right is also positive, so no triplet can sum to zero and you may break early.
Walkthrough: nums = [-1, 0, 1, 2, -1, -4]
After sorting: [-4, -1, -1, 0, 1, 2]. Anchor is nums[i], and the pointers search the range to its right.
| Step | i (anchor) | left | right | sum | Action |
|---|---|---|---|---|---|
| 1 | 0 (−4) | 1 (−1) | 5 (2) | −3 | sum < 0 → left++ |
| 2 | 0 (−4) | 2 (−1) | 5 (2) | −3 | sum < 0 → left++ |
| 3 | 0 (−4) | 3 (0) | 5 (2) | −2 | sum < 0 → left++ |
| 4 | 0 (−4) | 4 (1) | 5 (2) | −1 | sum < 0 → left++ → pointers meet |
| 5 | 1 (−1) | 2 (−1) | 5 (2) | 0 | found [−1, −1, 2] → left++, right-- |
| 6 | 1 (−1) | 3 (0) | 4 (1) | 0 | found [−1, 0, 1] → pointers cross |
| 7 | 2 (−1) | — | — | — | nums[2] === nums[1] → skip duplicate anchor |
| 8 | 3 (0) | 4 (1) | 5 (2) | 3 | sum > 0 → right-- → pointers meet |
Result: [[-1, -1, 2], [-1, 0, 1]]. Step 7 is the one that trips people up: the second -1 is skipped as an anchor, yet it was perfectly legal as a left value in step 5. Dedup rules out repeated anchors, not repeated values inside one triplet.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force + set | O(n³) | O(n) | three nested loops, plus hashing triplets to dedup |
| Hash map per anchor | O(n²) | O(n) | Two Sum with a map for each anchor; dedup stays messy |
| Sort + two pointers | O(n²) | O(1) extra | one sort (O(n log n)), then a linear pointer scan per anchor |
The sort costs O(n log n) but is dominated by the n anchors × O(n) scans that follow. Space is O(1) beyond the output. The hash-map variant matches the time but loses on space and forces you back into stringify-and-set deduplication — sorted adjacency is what makes dedup nearly free.
Common mistakes
- Deduplicating only the anchor. All three positions need skips: the anchor before the inner loop, and both
leftandrightafter every found triplet. Miss the inner ones and[0, 0, 0, 0]returns[0, 0, 0]multiple times. - Skipping duplicates by looking ahead (
nums[i] === nums[i + 1]) instead of behind (nums[i] === nums[i - 1]). Looking ahead skips the first occurrence too, which silently destroys valid triplets like[-1, -1, 2]. - Moving only one pointer after a match. With the anchor fixed, advancing just one side either repeats the triplet or loops forever once the skip-whiles are involved.
- Forgetting
left < rightinside the duplicate-skip whiles. On an all-equal array the skips march the pointers past each other and read out of bounds without that guard. - Refusing to sort out of Two Sum habit. Two Sum forbids sorting because it wants indices. 3Sum wants values, so sorting is not just allowed — it's the entire strategy.
Where this pattern shows up next
The fix-an-anchor-then-two-point discipline transfers well beyond triplets:
- Two Sum — the unsorted original, where a hash map replaces pointers because indices must survive.
- Two Sum II - Input Array Is Sorted — the exact inner loop of 3Sum, isolated as its own problem. Master it first and 3Sum is one wrapper loop away.
- Is Subsequence — two pointers walking forward together across two sequences instead of inward across one.
- Find the Index of the First Occurrence in a String — pointer alignment applied to substring matching.
Or open the 3Sum visualizer and watch the search window shrink and the triplets light up, one step at a time.
FAQ
Why does 3Sum sort the array first?
Sorting enables both halves of the solution. It gives the two pointers directional control — moving the left pointer rightward always increases the sum, moving the right pointer leftward always decreases it — so each anchor's pair search finishes in one O(n) pass. It also places equal values next to each other, turning duplicate elimination into a constant-time neighbor comparison. Since the problem asks for values rather than indices, sorting destroys nothing you need.
What is the time complexity of 3Sum?
O(n²) time and O(1) extra space (ignoring the output list). The initial sort is O(n log n), then each of the n anchor positions runs an O(n) two-pointer scan — n anchors × O(n) work = O(n²), which dominates the sort. The brute-force triple loop is O(n³), so the two-pointer version is roughly a 1000× speedup on a 1,000-element array.
How does 3Sum avoid duplicate triplets without a hash set?
By skipping repeated values at all three positions in the sorted array. The anchor skips any value equal to its predecessor (nums[i] === nums[i - 1]), because that value already generated every triplet it can appear in. After recording a match, both pointers slide past any run of equal neighbors before stepping inward. Because duplicates are adjacent after sorting, each skip is a simple comparison — no auxiliary set, no stringified keys.
Can I solve 3Sum with a hash map like Two Sum?
Yes — fix each anchor and run hash-map Two Sum on the remainder — and it also lands at O(n²) time. But it costs O(n) extra space for the map, and deduplication gets ugly: without sorted adjacency you end up hashing whole triplets into a set to filter repeats. The sorted two-pointer version matches the time, wins on space, and is the approach interviewers expect.
Why check nums[i] === nums[i - 1] instead of nums[i] === nums[i + 1]?
Looking backward skips repeat anchors while keeping the first occurrence; looking forward would skip the first occurrence itself. That distinction matters because a triplet may legally contain the same value twice — in [-4, -1, -1, 0, 1, 2], the answer [-1, -1, 2] needs the first -1 as the anchor and the second as the left pointer. Skip the first -1 and that triplet is unreachable.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.