ASAPUtils
The signal
Three numbers, a target sum, and a uniqueness requirement. The instinct is a triple loop — O(n³), too slow. The way out is the one move that shows up again and again in interviews:
Reduce a k-sum to a (k−1)-sum by fixing one element.
Fix nums[i], and the rest of the problem is “find two numbers summing to -nums[i]” — which is
Two Sum II, a problem you already know how to do in O(n).
Approach ladder
1. Triple loop — O(n³)
Every triple, then deduplicate. Too slow, and deduplicating a list of triplets is genuinely annoying.
2. Fix one, hash map the rest — O(n²)
Right complexity, but deduplication becomes painful because the input order gives you no help.
3. Sort first — and get two things at once
Sorting costs O(n log n), which is free next to O(n²), and it buys both of the hard parts:
- Two pointers become possible on the remaining subarray.
- Equal values become adjacent, which makes duplicate-skipping a single comparison instead of a set of seen triplets.
That second benefit is the one people miss, and it’s the more valuable of the two.
4. Optimal — O(n²)
vector<vector<int>> threeSum(vector<int>& a) {
sort(a.begin(), a.end());
vector<vector<int>> res;
for (int i = 0; i + 2 < (int)a.size(); i++) {
if (a[i] > 0) break; // sorted: nothing further can reach 0
if (i > 0 && a[i] == a[i-1]) continue; // skip duplicate fixed element
int l = i + 1, r = a.size() - 1;
while (l < r) {
int sum = a[i] + a[l] + a[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
res.push_back({a[i], a[l], a[r]});
l++; r--;
while (l < r && a[l] == a[l-1]) l++; // skip duplicate second element
}
}
}
return res;
}
function threeSum(a) {
a.sort((x, y) => x - y);
const res = [];
for (let i = 0; i + 2 < a.length; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] === a[i - 1]) continue;
let l = i + 1, r = a.length - 1;
while (l < r) {
const sum = a[i] + a[l] + a[r];
if (sum < 0) l++;
else if (sum > 0) r--;
else {
res.push([a[i], a[l], a[r]]);
l++; r--;
while (l < r && a[l] === a[l - 1]) l++;
}
}
}
return res;
}
The two duplicate skips, and why you need both
- Outer skip (
a[i] === a[i-1]): fixing the same value twice regenerates every triplet that value can be part of. Note it’si > 0 && a[i] === a[i-1], nota[i] === a[i+1]— you skip later copies, keeping the first. - Inner skip (after recording): the same second element paired with the same first element can only produce the same triplet again.
Drop either and you emit duplicates. This is the single most common reason a 3Sum submission fails, and it’s worth stepping through in the visualizer specifically.
Complexity
- Time O(n²) — n iterations of an O(n) two-pointer scan. The O(n log n) sort is dominated.
- Space O(1) auxiliary (ignoring the output and the sort’s internals).
Traps
- Only skipping duplicates in one place.
a[i] > 0break placed wrongly. It’s a real optimisation on a sorted array, but only valid because the target is 0.- Moving only one pointer after a hit. Move both — keeping either reproduces the same triplet.
- JavaScript
sort()without a comparator.[-1, 0, 1, 2, -1, -4].sort()is lexicographic and silently wrong.
Blank re-solve prompt
Return every unique triplet summing to zero, in O(n²). Get the duplicate handling right without using a set of seen triplets.