3Sum
Find every unique triplet in an array that adds up to zero by sorting first and then running two pointers for each fixed number, in O(n²) time.
Updated Medium read: 6 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force with a set of seen triplets | O(n³) | O(n) |
| Sort, then two pointers | O(n²) | O(n) |
The problem
Given an array of integers, return every set of three elements that adds up to zero. Each triplet must use three different positions in the array, and the result must not contain the same triplet twice, whatever order its numbers are in.
[-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
[0, 1, 1] → []
[0, 0, 0, 0] → [[0, 0, 0]]In the first example -1, 0 and 1 can be picked in two ways, because there are two -1s, but [-1, 0, 1] is listed once.
The space figures below do not count the list of triplets that is returned.
Approach 1: brute force
Try every combination of three positions. Sorting a copy first means each triplet always comes out in the same order, so a text key such as "-1,0,1" is enough to spot one that has been recorded already.
JavaScript
function threeSumBruteForce(numbers) {
const sorted = [...numbers].sort((a, b) => a - b);
const seen = new Set();
const triplets = [];
for (let i = 0; i < sorted.length; i++) {
for (let j = i + 1; j < sorted.length; j++) {
for (let k = j + 1; k < sorted.length; k++) {
if (sorted[i] + sorted[j] + sorted[k] !== 0) continue;
const key = `${sorted[i]},${sorted[j]},${sorted[k]}`;
if (seen.has(key)) continue;
seen.add(key);
triplets.push([sorted[i], sorted[j], sorted[k]]);
}
}
}
return triplets;
}Python
def three_sum_brute_force(numbers):
ordered = sorted(numbers)
seen = set()
triplets = []
for i in range(len(ordered)):
for j in range(i + 1, len(ordered)):
for k in range(j + 1, len(ordered)):
triplet = (ordered[i], ordered[j], ordered[k])
if sum(triplet) != 0 or triplet in seen:
continue
seen.add(triplet)
triplets.append(list(triplet))
return tripletsTime O(n³): three nested loops. Space O(n) for the sorted copy, plus the set of keys.
Approach 2: sort, then two pointers
Fix the first number of the triplet. What is left is a smaller question: find two numbers to its right that add up to the negative of the fixed number. On a sorted array that is exactly Two Sum on a Sorted Array, which two pointers solves in one pass.
So the plan is:
- Sort a copy of the array.
- For each position
i, putleftjust afteriandrightat the end. - If the three numbers add up to less than zero, move
leftup. If more, moverightdown. If exactly zero, record the triplet and move both.
Duplicates are handled by skipping, not by a set. Because equal values sit next to each other after sorting, it is enough to skip a fixed number that equals the one before it, and to skip a left value that equals the one just used.
JavaScript
function threeSum(numbers) {
const sorted = [...numbers].sort((a, b) => a - b);
const triplets = [];
for (let i = 0; i < sorted.length - 2; i++) {
if (sorted[i] > 0) break;
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
let left = i + 1;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
triplets.push([sorted[i], sorted[left], sorted[right]]);
left++;
right--;
while (left < right && sorted[left] === sorted[left - 1]) left++;
}
}
}
return triplets;
}Python
def three_sum(numbers):
ordered = sorted(numbers)
triplets = []
for i in range(len(ordered) - 2):
if ordered[i] > 0:
break
if i > 0 and ordered[i] == ordered[i - 1]:
continue
left = i + 1
right = len(ordered) - 1
while left < right:
total = ordered[i] + ordered[left] + ordered[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([ordered[i], ordered[left], ordered[right]])
left += 1
right -= 1
while left < right and ordered[left] == ordered[left - 1]:
left += 1
return tripletsThe early break is a small saving: once the fixed number is positive, everything to its right is positive too, and three positive numbers cannot add up to zero.
Walkthrough
[-1, 0, 1, 2, -1, -4] sorted is [-4, -1, -1, 0, 1, 2]:
| i (value) | left (value) | right (value) | Sum | Action |
|---|---|---|---|---|
| 0 (-4) | 1 (-1) | 5 (2) | -3 | Too small. left moves up four times and never reaches zero |
| 1 (-1) | 2 (-1) | 5 (2) | 0 | Record [-1, -1, 2], move both |
| 1 (-1) | 3 (0) | 4 (1) | 0 | Record [-1, 0, 1], move both; pointers cross |
| 2 (-1) | Same value as the previous i: skip |
|||
| 3 (0) | 4 (1) | 5 (2) | 3 | Too large, move right; pointers meet |
Time O(n²): sorting costs O(n log n), then each of the n fixed numbers gets one O(n) pass. Space O(n) for the sorted copy. Sorting the input in place would avoid the copy, at the price of changing the caller's array.
Why skipping duplicates is enough
There are two places a repeated triplet could come from.
- The same fixed value twice. With
ion the first-1, the inner loop finds every triplet that starts with-1. Starting again from the second-1could only find a subset of those, so it is skipped. The check issorted[i] === sorted[i - 1], comparing with the previous element, so the first copy is still used and[-1, -1, 2]is still found. - The same pair twice for one fixed value. After recording a triplet,
leftmoves past every copy of the value it just used. Onceleftholds a new value,rightmust hold a new value too for the sum to be zero, sorightneeds no skip loop of its own.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(threeSum([-1, 0, 1, 2, -1, -4])); // [[-1, -1, 2], [-1, 0, 1]]
console.log(threeSum([0, 0, 0, 0])); // [[0, 0, 0]]Python
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 0, 0, 0])) # [[0, 0, 0]]The comment after each line is the result you should see.
Common mistakes
- Forgetting the comparator when sorting.
sort()with no argument compares numbers as text, so-1lands after-4only by luck and10lands before2. Always pass(a, b) => a - b. - Skipping duplicates with
sorted[i] === sorted[i + 1]. That skips the first copy rather than the later ones and loses triplets such as[-1, -1, 2]. - Stopping at the first match. Unlike Two Sum, one fixed number can belong to several triplets, so keep going after recording one.
- Using a hash set of triplets in the fast version. It works, but it hides an avoidable cost; skipping equal neighbours needs no extra memory.
Original problem: LeetCode 15: 3Sum