Learn › DSA Patterns › Two Pointers › Case Study
3Sum:
4 Bugs to a Clean Solution
Not a tutorial — a real debugging log. Five attempts, four distinct bugs, each one reproduced with real, executed output before it was fixed.
The Problem
LeetCode 15 — 3Sum
Given an integer array nums, return
all unique triplets [nums[i], nums[j], nums[k]] such that
i !== j,
i !== k, and
j !== k, and
nums[i] + nums[j] + nums[k] === 0.
The solution set must not contain duplicate triplets.
Input
[-1,0,1,2,-1,-4] Output
[[-1,-1,2],[-1,0,1]] Input
[0,1,1] Output
[] Input
[0,0,0] Output
[[0,0,0]] The Journey
Attempt by Attempt
Every bug below was reproduced by actually running the code against real inputs — not just described.
function threeSum(nums: number[]): number[][] {
const sortedNums = nums.sort((a, b) => (b - a))
let results = []
for (let i = 0; i < nums.length - 3; i++) {
let left = i+1, right = nums.length -1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
results.push([i, left, right])
left++; right--;
} else if (sum > 0) right--
else left++
}
}
return results
};Compiles fine, runs fine — and returns nothing on the classic example.
Three independent mistakes stack up here. First, .sort((a, b) => b - a) sorts descending, which inverts the two-pointer branch logic — sum > 0 → right-- only converges correctly when larger values sit on the right (ascending order). Second, results.push([i, left, right]) pushes the loop indices instead of the actual numbers at those positions. Third, the loop bound i < nums.length - 3 excludes the last valid starting index — three elements are needed from i onward, which requires i < nums.length - 2, not - 3.
Proof — actual output on real inputs:
threeSum([-1,0,1,2,-1,-4]) → [] (WRONG — expected [[-1,-1,2],[-1,0,1]]) threeSum([0,0,0]) → [] (WRONG — expected [[0,0,0]]) threeSum([3,0,-2,-1,1,2]) → [] (WRONG — expected 3 triplets)
Sort ascending (a - b), push nums[i]/nums[left]/nums[right] instead of the indices, and change the loop bound to nums.length - 2.
function threeSum(nums: number[]): number[][] {
const sortedNums = nums.sort((a, b) => (a - b))
let results = []
for (let i = 0; i < nums.length - 2; i++) {
let left = i+1, right = nums.length -1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
results.push([nums[i], nums[left], nums[right]])
left++; right--;
} else if (sum > 0) right--
else left++
}
}
return results
};
// ⚠ no duplicate handling — repeated values in nums produce repeated tripletsAll three Attempt 1 bugs are fixed — but duplicate values in the input produce duplicate triplets.
With sort direction, pushed values, and the loop bound all correct, the algorithm now finds every valid triplet — but it finds some of them more than once. Any input with a repeated number can make the two-pointer scan and later outer-loop iterations land on the exact same triplet from different starting positions.
Proof — actual output on real inputs:
threeSum([-1,0,1,2,-1,-4]) → [[-1,-1,2],[-1,0,1],[-1,0,1]] (WRONG — [-1,0,1] appears twice) threeSum([-1,-1,0,1,1]) → [[-1,0,1],[-1,0,1]] (WRONG — same triplet twice)
Needs duplicate handling — but where that logic goes turns out to matter a lot (see Attempts 3 and 4).
function threeSum(nums: number[]): number[][] {
const sortedNums = nums.sort((a, b) => (a - b))
let results = []
for (let i = 0; i < nums.length - 2; i++) {
let left = i+1, right = nums.length -1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
results.push([nums[i], nums[left], nums[right]])
while(nums[left] === nums[left+1]) left++
while(nums[right] === nums[right-1]) right--
left++; right--;
} else if (sum > 0) right--
else left++
}
}
return results
};
// ⚠ left/right dedup added — but the outer i has no dedup of its ownSkipping repeated left/right values after a match helps — but the outer i loop has no dedup of its own.
After pushing a match, the code now skips past any repeated nums[left] or nums[right] values before advancing the pointers. That's correct, but it only prevents duplicates within a single i's inner scan. With nums = [-1,-1,0,1,1], both i = 0 and i = 1 have nums[i] === -1, and each one independently rediscovers the same [-1, 0, 1] triplet.
Proof — actual output on real inputs:
threeSum([-1,-1,0,1,1]) → [[-1,0,1],[-1,0,1]] (WRONG — still duplicated) threeSum([-1,0,1,2,-1,-4]) → [[-1,-1,2],[-1,0,1],[-1,0,1]] (WRONG — still duplicated)
Also skip repeated values of nums[i] in the outer loop — not just left/right.
function threeSum(nums: number[]): number[][] {
const sortedNums = nums.sort((a, b) => (a - b))
let results = []
for (let i = 0; i < nums.length - 2; i++) {
while(nums[i] === nums[i+1]) i++
let left = i+1, right = nums.length -1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
results.push([nums[i], nums[left], nums[right]])
while(nums[left] === nums[left+1]) left++
while(nums[right] === nums[right-1]) right--
left++; right--;
} else if (sum > 0) right--
else left++
}
}
return results
};
// ⚠ dedup runs BEFORE the search — skips a duplicate value before it's ever usedThe dedup check for i was added — but at the top of the loop, before the inner search ever runs.
while (nums[i] === nums[i+1]) i++ placed before the two-pointer scan skips past a duplicate value before it has ever been used. That breaks any triplet that legitimately needs two copies of the same number. For nums = [-1,-1,2], i jumps from 0 straight to 1 before searching, leaving left = right = 2 — the inner while (left < right) never runs at all, and the correct triplet is lost entirely.
Proof — actual output on real inputs:
threeSum([-1,-1,2]) → [] (WRONG — expected [[-1,-1,2]]) threeSum([0,0,0,0]) → [] (WRONG — expected [[0,0,0]]) threeSum([-1,0,1,2,-1,-4]) → [[-1,0,1]] (WRONG — missing [-1,-1,2] entirely)
Move the exact same dedup line to run AFTER the inner while (left < right) loop completes for that i, not before it.
function threeSum(nums: number[]): number[][] {
const sortedNums = nums.sort((a, b) => (a - b))
let results = []
for (let i = 0; i < nums.length - 2; i++) {
let left = i+1, right = nums.length -1
while (left < right) {
let sum = nums[i] + nums[left] + nums[right]
if (sum === 0) {
results.push([nums[i], nums[left], nums[right]])
while(nums[left] === nums[left+1]) left++
while(nums[right] === nums[right-1]) right--
left++; right--;
} else if (sum > 0) right--
else left++
}
while(nums[i] === nums[i+1]) i++
}
return results
};One change from Attempt 4: the outer dedup line moved from the top of the loop body to the bottom, after the inner two-pointer search has fully run for that i. This way a duplicate value gets used once before any of its repeats are skipped. Verified by actually running the code against 8 test cases, including the duplicate-heavy ones that broke every earlier attempt.
Proof — actual output on 8 real test cases:
[-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]] ✅ [0,1,1] → [] ✅ [0,0,0] → [[0,0,0]] ✅ [-1,-1,2] → [[-1,-1,2]] ✅ [0,0,0,0] → [[0,0,0]] ✅ [3,0,-2,-1,1,2] → [[-2,-1,3],[-2,0,2],[-1,0,1]] ✅ [-2,0,0,2,2] → [[-2,0,2]] ✅ [1,-1,-1,0] → [[-1,0,1]] ✅
Lessons Learned
Key Takeaways
Sort direction must match your two-pointer branch logic
sum > 0 → right-- only converges correctly when the array is sorted ascending. A descending sort inverts that reasoning — the pointers still move, but they rarely converge on a real answer.
Push the actual values, not the loop indices
results.push([i, left, right]) is an easy slip when i, left, and right are already the variables in scope — but the problem wants the numbers at those positions, not their positions.
Two-pointer bounds need i < nums.length - 2
Three slots are required from i onward (i, left, right), so the outer loop must stop two short of the end — not three. Off-by-one here silently drops the last valid starting index.
Duplicate triplets can leak from two independent places
The inner left/right pointers and the outer i loop each need their own dedup check. Fixing one without the other still leaves duplicates — as Attempt 3 showed.
Dedup must happen after a value is used, not before
Skipping a duplicate value before its first use throws away legitimate triplets that need that value twice, like [-1, -1, 2]. Dedup goes after the search, not before it.
Final Result
The Verified Solution
Sorts in place, then fixes one number and two-pointers the rest.
// O(N²) time, O(1) extra space — sort in place + two pointers
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const results: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) {
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
results.push([nums[i], nums[left], nums[right]]);
while (nums[left] === nums[left + 1]) left++;
while (nums[right] === nums[right - 1]) right--;
left++; right--;
} else if (sum > 0) right--;
else left++;
}
while (nums[i] === nums[i + 1]) i++;
}
return results;
}| Solution | Time | Space | Verified |
|---|---|---|---|
| Sort + Two Pointers (Attempt 5) Verified ✓ | O(N²) | O(1) | 8/8 real test cases, incl. duplicate-heavy edge cases |
Keep Learning
Bugs are part of the process 🎉
Four real bugs, four real fixes — that's what getting to a correct Two Pointers solution actually looks like.