March 24
3Sum
How to reduce a three-variable problem into two pointers after sorting and handling duplicates in a controlled way.
Arrays and Two Pointers Intermediate 25 min TypeScript
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that:
i != ji != kj != knums[i] + nums[j] + nums[k] === 0
The solution set must not contain duplicate triplets.
Example:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
What to notice before coding
- The answer asks for unique triplets, so duplicates matter.
- After fixing one element, the remaining problem looks like Two Sum.
- Sorting changes everything because it enables two pointers and duplicate skipping.
Common mistakes
- forgetting to sort before applying two pointers
- finding a valid triplet and not skipping duplicates afterward
Step 1 — Write the mental baseline without running from it
The first natural read is:
- choose a first number
- choose a second
- choose a third
- test whether they sum to zero
That becomes three loops.
Correct. But too expensive.
Step 2 — Look for a reduction
If you fix nums[i], you are no longer searching for three numbers.
Now you only need two numbers in the remaining range that satisfy:
nums[left] + nums[right] = -nums[i]
That already looks like Two Sum.
Step 3 — Understand why sorting helps
After sorting:
- if the sum is too small, you need a bigger value
- if the sum is too large, you need a smaller value
That is what allows left and right to work.
Step 4 — Remember that duplicates are part of the problem
Solving the sum is not enough.
After finding a valid triplet, you need to skip repeated values so you do not generate the same answer again.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function threeSum(nums: number[]): number[][] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n²)
Space: O(1)
Solution 1 — Three loops O(n³)
Good baseline to show the raw problem.
export function threeSum(nums: number[]): number[][] {
const result: number[][] = []
const seen = new Set<string>()
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
for (let k = j + 1; k < nums.length; k += 1) {
if (nums[i] + nums[j] + nums[k] === 0) {
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
}It works, but it is far too heavy.
Solution 2 — Sort + two pointers O(n²)
Now the three-number problem becomes a repeated two-number problem for each fixed index.
export function threeSum(nums: number[]): number[][] {
const sorted = [...nums].sort((a, b) => a - b)
const result: number[][] = []
for (let index = 0; index < sorted.length - 2; index += 1) {
const value = sorted[index]
if (index > 0 && value === sorted[index - 1]) {
continue
}
let left = index + 1
let right = sorted.length - 1
while (left < right) {
const sum = value + sorted[left] + sorted[right]
if (sum === 0) {
result.push([value, sorted[left], sorted[right]])
left += 1
right -= 1
while (left < right && sorted[left] === sorted[left - 1]) {
left += 1
}
while (left < right && sorted[right] === sorted[right + 1]) {
right -= 1
}
continue
}
if (sum < 0) {
left += 1
} else {
right -= 1
}
}
}
return result
}The important step is not sorting by itself. It is what sorting lets you do afterward.
What to say in the interview
A strong short explanation would be:
The baseline tests all triplets and costs
O(n³). The better version sorts the array, fixes one element, and reduces the rest to a two pointers problem. That lets me adjust the sum by movingleftandright, while also handling duplicates during the pass.
That shows that you:
- decomposed the problem correctly
- connected 3Sum to a pattern you already knew
- explained deduplication as part of the rule, not a random detail
When this pattern shows up again
The same pattern comes back when you need to:
- fix part of the answer and solve the rest
- combine sorting with two pointers
- control duplicates in combination problems
- reduce search dimension with structure
The point is not memorizing
3Sum.
The point is learning how to reduce a bigger problem into a smaller familiar one.