Sort the array, fix one index i, and squeeze two pointers inward — the sorted order lets you steer toward zero and skip duplicates with a single comparison, yielding all unique zero-sum triplets in O(n²) time.
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. No duplicate triplets in the output. nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]. The same three indices can't be reused, and the answer set must contain no duplicate tuples.
nums[i] reduces the problem to “find two numbers in a sorted subarray that sum to -nums[i].” Two pointers from both ends either find a match or tell you unambiguously which direction to move — because the array is sorted, moving l right only increases the sum and moving r left only decreases it.nums.sort() ascending. This enables pointer steering and lets duplicate detection be a single equality check with the neighbor.i from 0 to n-3. Skip if nums[i] === nums[i-1] (duplicate outer value). Break if nums[i] > 0 (no positive triple can sum to zero after sorting).l = i+1, r = n-1. While l < r: compute sum = nums[i]+nums[l]+nums[r]. If sum === 0 record it; if sum < 0 advance l; if sum > 0 retreat r.l past repeats and retreat r past repeats before moving both pointers inward. This avoids recording the same triple again.l (or only r) still produces duplicates for inputs like [-2, 0, 0, 0, 2]. Both inner duplicate-skip loops are required.The in-place sort uses O(log n) call-stack space. The output list itself is O(k) for k results, which is unavoidable. A hash-set approach also achieves O(n²) but requires O(n) auxiliary space and is harder to deduplicate cleanly — the two-pointer approach handles duplicates structurally.
minDiff instead of exact zero), and 3Sum Smaller(count pairs below a target). Anywhere you see “k-sum, sorted input, unique tuples,” reach for nested pointers.-1, 0, 1, 2, -1, -4. Step 1: sort the array so two-pointer math works and duplicate-skipping is trivial.function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const result: number[][] = [];
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
if (nums[i] > 0) break; // sorted: smallest value > 0 => no solution
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip dup i
let l = i + 1, r = n - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l + 1]) l++; // skip dup l
while (l < r && nums[r] === nums[r - 1]) r--; // skip dup r
l++;
r--;
} else if (sum < 0) {
l++; // sum too small: larger l needed
} else {
r--; // sum too large: smaller r needed
}
}
}
return result;
}if (nums[i] > 0) break works because the array is sorted: if the smallest remaining element is positive, no triple can sum to zero. if (i > 0 && nums[i] === nums[i-1]) continue skips a duplicate outer value so we never generate the same triplet from two different positions of the same number.l starts just right of i; r starts at the end. A sum less than zero means we need a larger value, so l++; a sum greater than zero means we need a smaller value, so r--. This is the core steering logic that makes the inner pass O(n) instead of O(n²).l past any duplicate values and retreat r past any duplicate values before moving both inward. Both loops are necessary — missing either one causes repeated triplets when two of the three values repeat.sum === 0 branch with tracking minDiff = Math.abs(sum - target). Update a running best when you find a closer sum.continue. That's simpler but produces repeats for inputs with repeated values.| "k unique integers summing to target" | sort + nested two pointers |
| no duplicate tuples in output | skip-neighbor check at each pointer level |
| find pair in sorted subarray summing to X | l/r squeeze from both ends |
| "3Sum Closest / 3Sum Smaller" | same skeleton, change termination condition |
nums.sort((a, b) => a - b);
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let l = i + 1, r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
result.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l + 1]) l++;
while (l < r && nums[r] === nums[r - 1]) r--;
l++; r--;
} else if (sum < 0) { l++; } else { r--; }
}
}
return result;break when nums[i] > 0 correct?nums = [-2, 0, 0, 2, 2]. How many unique triplets are in the answer?nums = [-1, 0, 1, 2, -1, -4] (the default example), what are the two unique triplets?