Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i, j, and k are distinct indices and nums[i] + nums[j] + nums[k] === 0.
The result must not contain duplicate triplets — two triplets are considered the same if they consist of the same three values (regardless of order). You may return the triplets, and the values within each triplet, in any order.
Example
The distinct triplets summing to 0 are [-1, -1, 2] and [-1, 0, 1].
Constraints
- 3 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
Intuition
A first pass just checks every possible triple of numbers and keeps the ones that sum to zero, using a set to throw out duplicate triplets.
function threeSum(nums) {
// A set of triplet keys, so the same triple is never added twice.
const seen = new Set();
const res = [];
// Check every distinct triple of indexes.
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) {
// Sort the values so [-1,0,1] and [1,-1,0] map to the same key.
const key = [nums[i], nums[j], nums[k]].sort((a, b) => a - b).join(',');
if (!seen.has(key)) {
seen.add(key);
res.push(key.split(',').map(Number)); // key string -> numbers
}
}
}
}
}
return res;
}This is O(n³) — far more work than necessary. Can we do better?
Notice that if we fix one number nums[i], the rest of the job is just finding a pair that sums to -nums[i] — which is exactly the Two pointers pair-sum problem.
Pair Sum's two-pointer trick only works on a sorted array, so sort the input first. Then, for each fixed i, converge two pointers over the suffix: move left up when the pair sum is too small, right down when it's too large, skipping equal neighbours so duplicates don't slip in.
Walking it through:
sorted: [-4, -1, -1, 0, 1, 2]
Fix i = -4: we need a pair summing to 4.
Even the two largest values fall short — nothing pairs with -4 to reach 0.
Fix i = -1: record the triplet [-1, -1, 2], then move both pointers in.
Another hit: [-1, 0, 1]. Record, move both in. (L and R then cross — this pivot is done.)
Index 2 is another -1; skip it as a pivot, or we'd emit [-1, -1, 2] and [-1, 0, 1] a second time.
Optimization
Sort + two pointers
Sort the array. Fix each value nums[i] as the smallest of the triplet, then find pairs that sum to -nums[i] in the suffix using two pointers converging from both ends: advance the low pointer when the sum is too small, retreat the high pointer when it's too large. Skip equal neighbours at every level (the fixed index, and after recording a hit on both pointers) to avoid duplicate triplets.
O(n²) time, O(1) extra space (ignoring the sort and output).
function threeSum(nums) {
// Sort so equal values sit together and pairs can be found by converging pointers.
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
// Fix each value as the smallest of the triplet.
for (let i = 0; i < sorted.length - 2; i++) {
// Skip a repeated pivot — it would only re-find the same triplets.
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
// Look for a pair in the suffix summing to -sorted[i].
let lo = i + 1;
let hi = sorted.length - 1;
while (lo < hi) {
const sum = sorted[i] + sorted[lo] + sorted[hi];
if (sum < 0) {
lo++; // sum too small — raise the low value
} else if (sum > 0) {
hi--; // sum too large — lower the high value
} else {
// Exact hit: record the triplet.
result.push([sorted[i], sorted[lo], sorted[hi]]);
// Skip duplicate values on both ends before continuing.
while (lo < hi && sorted[lo] === sorted[lo + 1]) lo++;
while (lo < hi && sorted[hi] === sorted[hi - 1]) hi--;
lo++;
hi--;
}
}
}
return result;
}Complexity analysis
Time complexity: O(n²). Here's why:
- Sorting the array takes O(n log n).
- Then, for each of the
nvalues, a two-pointer scan over the suffix runs in O(n).
So the scans cost n × O(n) = O(n²), which dominates the sort — the overall time is O(n²).
Space complexity: O(n). Here's why:
- The sorted copy of the input takes O(n) (plus the sort's own bookkeeping).
- The two-pointer scan itself uses only a handful of variables — O(1).
The output array isn't counted as auxiliary space; if it were, it could hold up to O(n²) triplets in the worst case.
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [] | [] | Empty array — nothing to pair. |
| nums = [0] | [] | Single element; a triplet needs three. |
| nums = [0,0] | [] | Two elements — still no triplet. |
| nums = [0,0,0] | [[0,0,0]] | All zeros — exactly one valid triplet. |
| nums = [1,2,3] | [] | All positive; nothing can sum to 0. |
| nums = [-2,0,1,1,2] | [[-2,0,2],[-2,1,1]] | Duplicates that must not yield repeated triplets. |
Try it yourself
Write your solution against the real judge before checking the reference.