Given an array of numbers, find every unique group of three values that add up to a target. This is the classic 3Sum problem — a staple interview question because the obvious answer is a slow triple loop, and the good answer teaches a reusable trick: sort the array, then sweep it with two pointers. The hard part is not the arithmetic, it's returning each distinct triplet exactly once even when the input is full of duplicates.
// nums: number[] — the input array (may contain duplicates, may be empty)
// target: number — the sum each triplet must hit; defaults to 0
// returns: number[][]
// Every UNIQUE triplet [a, b, c] of values taken from THREE DIFFERENT
// positions in nums, where a + b + c === target.
// Output convention (so the result is deterministic):
// - each triplet is sorted ascending: a <= b <= c
// - the list of triplets is sorted ascending too (by a, then b, then c)
function tripletSum(nums: number[], target?: number): number[][];A triplet uses three distinct positions, but those positions may hold equal values — [0, 0, 0] is a valid triplet if three different slots all hold 0.
// The classic case. target defaults to 0.
tripletSum([-1, 0, 1, 2, -1, -4]);
// → [[-1, -1, 2], [-1, 0, 1]]
// Note: only TWO triplets, even though -1 appears twice — the duplicate
// pairing [-1, 0, 1] is not repeated.// No three values sum to the target → empty array.
tripletSum([1, 2, 3, 4], 100); // → []// A non-zero target, with the result still sorted both ways.
tripletSum([1, 1, 2, 3, 4], 6); // → [[1, 1, 4], [1, 2, 3]][-1, -1, 2] appears a single time in the output regardless of how many -1s are in the input.[]. There is no triplet to form.target parameter is optional and defaults to 0, but it must work for any number (negative, positive, or zero).k — those are out of scope (see Going further in the solution).You'll find every distinct group of three values in an array that add up to a target, and you'll do it without checking all three-way combinations.
You have a bag of numbers and a target sum. You want every distinct trio of numbers — drawn from three different positions — that totals the target. Think of a budgeting tool where each number is a transaction and you're hunting for any three that net to zero, or a chemistry app looking for three reagents whose charges cancel. The catch that makes this more than a loop: if the same trio of values can be assembled in several ways because the input repeats values, you must report it once, not once per arrangement.
Two ideas do all the work. Sorting turns the array into something you can scan with direction — bigger values are always to the right. And once one value is pinned down, the remaining two-of-them search collapses into a two-pointer sweep that walks in from both ends. Sorting also lines up duplicates next to each other, which is what makes deduping cheap.
Sort the array first. Now walk an index i from left to right; at each stop, nums[i] is the first member of any triplet that starts here. The job shrinks to: in the slice to the right of i, find two values that sum to target - nums[i]. Put one pointer (left) just after i and another (right) at the end, and move them toward each other.
Why two pointers instead of a nested loop over the slice? Because the slice is sorted, the sum at any (left, right) pair tells you which way to move. Too small? The only way to grow it is to pull left rightward onto a bigger value. Too big? Pull right leftward onto a smaller one. Each step eliminates a whole row or column of pairs you'd otherwise test — that's how a quadratic-per-slice search becomes linear-per-slice.
The most direct reading of the problem is three nested loops over distinct positions i < j < k, collecting every trio that hits the target. The only wrinkle is dedup: two different index-trios can produce the same value-triplet, so we sort each found triplet and stash a string key in a Set to suppress repeats.
function tripletSumNaive(nums, target = 0) {
const seen = new Set(); // string keys of triplets we've already recorded
const result = [];
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === target) {
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;
}This is correct — it really does return every unique triplet. But it does O(n³) work: for an array of 1,000 numbers that's on the order of a billion iterations. The dedup is also awkward and easy to get subtly wrong — you have to remember to sort each triplet before building the key, or [−1, 2, −1] and [−1, −1, 2] hash to different strings and you double-count. The Set of string keys is extra memory that exists only to paper over the fact that the loop visits the same value-triplet from many index combinations. Sorting the input up front removes the need for all of it.
Sort once. Then for each i, run the two-pointer sweep, and skip over duplicate values at three places: at i, and at left and right after a match.
function tripletSum(nums, target = 0) {
// Sort ascending. This is the move that powers everything below:
// directional pointers, in-order output, and cheap duplicate-skipping.
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
const n = sorted.length;
for (let i = 0; i < n - 2; i++) {
// Skip a repeated FIRST value: if nums[i] equals the previous value we
// already fixed, every triplet starting here was found starting there.
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
let left = i + 1;
let right = n - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (sum === target) {
result.push([sorted[i], sorted[left], sorted[right]]);
// Step both pointers PAST their duplicates so the next pair is a
// genuinely different triplet, not the same one re-read.
while (left < right && sorted[left] === sorted[left + 1]) left++;
while (left < right && sorted[right] === sorted[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++; // sum too small — only a larger value can fix it
} else {
right--; // sum too large — only a smaller value can fix it
}
}
}
return result;
}
module.exports = { tripletSum };The key shift from the naive version: sorting does triple duty. It lets the pointers move with purpose (so each slice is a single linear pass instead of a nested loop), it places equal values side by side (so a one-line === next check skips them, replacing the whole Set), and it means we build triplets in ascending order — both within each triplet and across the list — so the documented output convention falls out for free without a final sort. The whole thing is O(n²): an outer loop over i and a linear inner sweep, on top of the O(n log n) sort.
A few lines deserve their why:
const sorted = [...nums].sort(...) copies first. Array.prototype.sort mutates in place; copying avoids surprising the caller by reordering the array they passed in.i < n - 2 stops the outer loop two from the end. A triplet needs an i, a left, and a right; once fewer than three slots remain there is nothing to form, so we don't even start. This is also what makes "fewer than three elements" return [] — the loop body never runs.if (i > 0 && sorted[i] === sorted[i - 1]) continue dedupes the first value. The i > 0 guard is essential: at i === 0 there is no previous element, and skipping based on sorted[-1] (which is undefined) would be a bug.while loops after a match are the duplicate-skip for the pair. After recording [sorted[i], sorted[left], sorted[right]], any neighbour equal to sorted[left] would rebuild the identical triplet, and likewise for right. We advance past them, then do the final left++; right-- to land on the next untried pair.Let's run tripletSum([-1, 0, 1, 2, -1, -4]) with the default target = 0. After the copy-and-sort, sorted = [-4, -1, -1, 0, 1, 2] (indices 0–5).
i = 0 → sorted[i] = -4, need left+right = 4
left=1(-1) right=5(2): -4 + -1 + 2 = -3 < 0 → left++
left=2(-1) right=5(2): -4 + -1 + 2 = -3 < 0 → left++
left=3( 0) right=5(2): -4 + 0 + 2 = -2 < 0 → left++
left=4( 1) right=5(2): -4 + 1 + 2 = -1 < 0 → left++
left=5, left < right is false → done with i=0. No triplet starts at -4.
i = 1 → sorted[i] = -1, need left+right = 1
left=2(-1) right=5(2): -1 + -1 + 2 = 0 === target → record [-1, -1, 2]
skip dups: sorted[left]=-1, sorted[left+1]=0 → no skip
sorted[right]=2, sorted[right-1]=1 → no skip
left++ → 3, right-- → 4
left=3( 0) right=4(1): -1 + 0 + 1 = 0 === target → record [-1, 0, 1]
left++ → 4, right-- → 3
left < right is false → done with i=1.
i = 2 → sorted[2] (-1) === sorted[1] (-1) → continue (skip the repeated first value)
i = 3 → sorted[i] = 0, need left+right = 0
left=4(1) right=5(2): 0 + 1 + 2 = 3 > 0 → right--
left=4, left < right is false → done.
return [[-1, -1, 2], [-1, 0, 1]]
Two things to watch. At i = 1 we found [-1, -1, 2] and then immediately found [-1, 0, 1] in the same sweep — one fixed i can yield several triplets. And at i = 2 the first-value skip fired: sorted[2] is another -1, and any triplet beginning with -1 was already collected when i was 1. Without that continue, we'd produce [-1, -1, 2] and [-1, 0, 1] a second time. The result is already sorted within each triplet and across the list, matching the contract with no extra sorting pass.
The payoff over the brute force is the whole point of sorting: one fixed value plus a linear sweep, instead of three nested loops and a Set.
[-1, 2, -1] and [-1, -1, 2] are one triplet. The naive Set only works if you sort each triplet before keying it; forget that and you double-count. The sorted-array approach sidesteps this entirely because values come out in order.i). On [-1, -1, 0, 1], both -1s would launch their own sweep and each find [-1, 0, 1], so the triplet appears twice. The if (i > 0 && sorted[i] === sorted[i - 1]) continue guard collapses those repeats — but the i > 0 half matters: without it, i = 0 compares against sorted[-1] (undefined) and you risk skipping the very first value.left and right past their equal neighbours. On [-2, 0, 0, 2, 2], skipping only left's duplicates still lets right re-pair to rebuild [-2, 0, 2]. Both while loops are required.sum === target, advancing only left (or only right) keeps the other end fixed; since the array is sorted, the sum then necessarily moves away from the target in one direction and you may loop without progress or miss pairs. After recording a match, step left++ and right--.nums.sort(...) mutates the caller's array. Copy with [...nums] (or nums.slice()) first — a function that silently reorders its input is a nasty surprise to debug.target is zero. The classic 3Sum is target 0, and it's tempting to hard-code that. Keep target a parameter and compare sum === target; the pointer-movement logic (sum < target / sum > target) is identical for negative, positive, or zero targets. A negative target just means the answers live further left in the sorted array.k-tuples summing to target." Sort once, then recurse: fix the first element and solve (k−1)-Sum on the rest, bottoming out at the two-pointer sweep for k = 2. Each added dimension costs one more outer loop, giving O(n^(k−1)) — O(n²) for 3Sum, O(n³) for 4Sum — with duplicate-skipping at every level.target. Same sort and two-pointer sweep, but track the best |sum − target| seen and move the pointers by the sign of sum − target exactly as here. No dedup needed since you return a single triplet.result array and increment a counter — but be careful counting duplicates: with equal values you'd count combinations (e.g. choosing 2 of 3 equal elements), which is a different question from counting distinct value-triplets. Decide which you mean before you optimize.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Given an array of numbers, find every unique group of three values that add up to a target. This is the classic 3Sum problem — a staple interview question because the obvious answer is a slow triple loop, and the good answer teaches a reusable trick: sort the array, then sweep it with two pointers. The hard part is not the arithmetic, it's returning each distinct triplet exactly once even when the input is full of duplicates.
// nums: number[] — the input array (may contain duplicates, may be empty)
// target: number — the sum each triplet must hit; defaults to 0
// returns: number[][]
// Every UNIQUE triplet [a, b, c] of values taken from THREE DIFFERENT
// positions in nums, where a + b + c === target.
// Output convention (so the result is deterministic):
// - each triplet is sorted ascending: a <= b <= c
// - the list of triplets is sorted ascending too (by a, then b, then c)
function tripletSum(nums: number[], target?: number): number[][];A triplet uses three distinct positions, but those positions may hold equal values — [0, 0, 0] is a valid triplet if three different slots all hold 0.
// The classic case. target defaults to 0.
tripletSum([-1, 0, 1, 2, -1, -4]);
// → [[-1, -1, 2], [-1, 0, 1]]
// Note: only TWO triplets, even though -1 appears twice — the duplicate
// pairing [-1, 0, 1] is not repeated.// No three values sum to the target → empty array.
tripletSum([1, 2, 3, 4], 100); // → []// A non-zero target, with the result still sorted both ways.
tripletSum([1, 1, 2, 3, 4], 6); // → [[1, 1, 4], [1, 2, 3]][-1, -1, 2] appears a single time in the output regardless of how many -1s are in the input.[]. There is no triplet to form.target parameter is optional and defaults to 0, but it must work for any number (negative, positive, or zero).k — those are out of scope (see Going further in the solution).You'll find every distinct group of three values in an array that add up to a target, and you'll do it without checking all three-way combinations.
You have a bag of numbers and a target sum. You want every distinct trio of numbers — drawn from three different positions — that totals the target. Think of a budgeting tool where each number is a transaction and you're hunting for any three that net to zero, or a chemistry app looking for three reagents whose charges cancel. The catch that makes this more than a loop: if the same trio of values can be assembled in several ways because the input repeats values, you must report it once, not once per arrangement.
Two ideas do all the work. Sorting turns the array into something you can scan with direction — bigger values are always to the right. And once one value is pinned down, the remaining two-of-them search collapses into a two-pointer sweep that walks in from both ends. Sorting also lines up duplicates next to each other, which is what makes deduping cheap.
Sort the array first. Now walk an index i from left to right; at each stop, nums[i] is the first member of any triplet that starts here. The job shrinks to: in the slice to the right of i, find two values that sum to target - nums[i]. Put one pointer (left) just after i and another (right) at the end, and move them toward each other.
Why two pointers instead of a nested loop over the slice? Because the slice is sorted, the sum at any (left, right) pair tells you which way to move. Too small? The only way to grow it is to pull left rightward onto a bigger value. Too big? Pull right leftward onto a smaller one. Each step eliminates a whole row or column of pairs you'd otherwise test — that's how a quadratic-per-slice search becomes linear-per-slice.
The most direct reading of the problem is three nested loops over distinct positions i < j < k, collecting every trio that hits the target. The only wrinkle is dedup: two different index-trios can produce the same value-triplet, so we sort each found triplet and stash a string key in a Set to suppress repeats.
function tripletSumNaive(nums, target = 0) {
const seen = new Set(); // string keys of triplets we've already recorded
const result = [];
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === target) {
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;
}This is correct — it really does return every unique triplet. But it does O(n³) work: for an array of 1,000 numbers that's on the order of a billion iterations. The dedup is also awkward and easy to get subtly wrong — you have to remember to sort each triplet before building the key, or [−1, 2, −1] and [−1, −1, 2] hash to different strings and you double-count. The Set of string keys is extra memory that exists only to paper over the fact that the loop visits the same value-triplet from many index combinations. Sorting the input up front removes the need for all of it.
Sort once. Then for each i, run the two-pointer sweep, and skip over duplicate values at three places: at i, and at left and right after a match.
function tripletSum(nums, target = 0) {
// Sort ascending. This is the move that powers everything below:
// directional pointers, in-order output, and cheap duplicate-skipping.
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
const n = sorted.length;
for (let i = 0; i < n - 2; i++) {
// Skip a repeated FIRST value: if nums[i] equals the previous value we
// already fixed, every triplet starting here was found starting there.
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
let left = i + 1;
let right = n - 1;
while (left < right) {
const sum = sorted[i] + sorted[left] + sorted[right];
if (sum === target) {
result.push([sorted[i], sorted[left], sorted[right]]);
// Step both pointers PAST their duplicates so the next pair is a
// genuinely different triplet, not the same one re-read.
while (left < right && sorted[left] === sorted[left + 1]) left++;
while (left < right && sorted[right] === sorted[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++; // sum too small — only a larger value can fix it
} else {
right--; // sum too large — only a smaller value can fix it
}
}
}
return result;
}
module.exports = { tripletSum };The key shift from the naive version: sorting does triple duty. It lets the pointers move with purpose (so each slice is a single linear pass instead of a nested loop), it places equal values side by side (so a one-line === next check skips them, replacing the whole Set), and it means we build triplets in ascending order — both within each triplet and across the list — so the documented output convention falls out for free without a final sort. The whole thing is O(n²): an outer loop over i and a linear inner sweep, on top of the O(n log n) sort.
A few lines deserve their why:
const sorted = [...nums].sort(...) copies first. Array.prototype.sort mutates in place; copying avoids surprising the caller by reordering the array they passed in.i < n - 2 stops the outer loop two from the end. A triplet needs an i, a left, and a right; once fewer than three slots remain there is nothing to form, so we don't even start. This is also what makes "fewer than three elements" return [] — the loop body never runs.if (i > 0 && sorted[i] === sorted[i - 1]) continue dedupes the first value. The i > 0 guard is essential: at i === 0 there is no previous element, and skipping based on sorted[-1] (which is undefined) would be a bug.while loops after a match are the duplicate-skip for the pair. After recording [sorted[i], sorted[left], sorted[right]], any neighbour equal to sorted[left] would rebuild the identical triplet, and likewise for right. We advance past them, then do the final left++; right-- to land on the next untried pair.Let's run tripletSum([-1, 0, 1, 2, -1, -4]) with the default target = 0. After the copy-and-sort, sorted = [-4, -1, -1, 0, 1, 2] (indices 0–5).
i = 0 → sorted[i] = -4, need left+right = 4
left=1(-1) right=5(2): -4 + -1 + 2 = -3 < 0 → left++
left=2(-1) right=5(2): -4 + -1 + 2 = -3 < 0 → left++
left=3( 0) right=5(2): -4 + 0 + 2 = -2 < 0 → left++
left=4( 1) right=5(2): -4 + 1 + 2 = -1 < 0 → left++
left=5, left < right is false → done with i=0. No triplet starts at -4.
i = 1 → sorted[i] = -1, need left+right = 1
left=2(-1) right=5(2): -1 + -1 + 2 = 0 === target → record [-1, -1, 2]
skip dups: sorted[left]=-1, sorted[left+1]=0 → no skip
sorted[right]=2, sorted[right-1]=1 → no skip
left++ → 3, right-- → 4
left=3( 0) right=4(1): -1 + 0 + 1 = 0 === target → record [-1, 0, 1]
left++ → 4, right-- → 3
left < right is false → done with i=1.
i = 2 → sorted[2] (-1) === sorted[1] (-1) → continue (skip the repeated first value)
i = 3 → sorted[i] = 0, need left+right = 0
left=4(1) right=5(2): 0 + 1 + 2 = 3 > 0 → right--
left=4, left < right is false → done.
return [[-1, -1, 2], [-1, 0, 1]]
Two things to watch. At i = 1 we found [-1, -1, 2] and then immediately found [-1, 0, 1] in the same sweep — one fixed i can yield several triplets. And at i = 2 the first-value skip fired: sorted[2] is another -1, and any triplet beginning with -1 was already collected when i was 1. Without that continue, we'd produce [-1, -1, 2] and [-1, 0, 1] a second time. The result is already sorted within each triplet and across the list, matching the contract with no extra sorting pass.
The payoff over the brute force is the whole point of sorting: one fixed value plus a linear sweep, instead of three nested loops and a Set.
[-1, 2, -1] and [-1, -1, 2] are one triplet. The naive Set only works if you sort each triplet before keying it; forget that and you double-count. The sorted-array approach sidesteps this entirely because values come out in order.i). On [-1, -1, 0, 1], both -1s would launch their own sweep and each find [-1, 0, 1], so the triplet appears twice. The if (i > 0 && sorted[i] === sorted[i - 1]) continue guard collapses those repeats — but the i > 0 half matters: without it, i = 0 compares against sorted[-1] (undefined) and you risk skipping the very first value.left and right past their equal neighbours. On [-2, 0, 0, 2, 2], skipping only left's duplicates still lets right re-pair to rebuild [-2, 0, 2]. Both while loops are required.sum === target, advancing only left (or only right) keeps the other end fixed; since the array is sorted, the sum then necessarily moves away from the target in one direction and you may loop without progress or miss pairs. After recording a match, step left++ and right--.nums.sort(...) mutates the caller's array. Copy with [...nums] (or nums.slice()) first — a function that silently reorders its input is a nasty surprise to debug.target is zero. The classic 3Sum is target 0, and it's tempting to hard-code that. Keep target a parameter and compare sum === target; the pointer-movement logic (sum < target / sum > target) is identical for negative, positive, or zero targets. A negative target just means the answers live further left in the sorted array.k-tuples summing to target." Sort once, then recurse: fix the first element and solve (k−1)-Sum on the rest, bottoming out at the two-pointer sweep for k = 2. Each added dimension costs one more outer loop, giving O(n^(k−1)) — O(n²) for 3Sum, O(n³) for 4Sum — with duplicate-skipping at every level.target. Same sort and two-pointer sweep, but track the best |sum − target| seen and move the pointers by the sign of sum − target exactly as here. No dedup needed since you return a single triplet.result array and increment a counter — but be careful counting duplicates: with equal values you'd count combinations (e.g. choosing 2 of 3 equal elements), which is a different question from counting distinct value-triplets. Decide which you mean before you optimize.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.