3Sum
MediumTwo pointers
Given an array of integers nums, return every triplet of values that adds up to zero, where the three values come from three different positions.
Each triplet should appear once: [-1, 0, 1] and [0, 1, -1] are the same triplet. The triplets, and the numbers inside each, can be in any order.
Examples
Input: nums = [-2, 0, 1, 1, 2] Output: [[-2, 0, 2], [-2, 1, 1]]
-2 + 0 + 2 and -2 + 1 + 1 are both zero.
Input: nums = [1, 2, 3] Output: []
No three of them add up to zero.
Constraints
3 ≤ nums.length ≤ 3000-10⁵ ≤ nums[i] ≤ 10⁵
Stuck?
Hint 1
Sort the array first. Then fix the first number and look for two more that add up to its negative.
Hint 2
In the sorted rest, move a left and a right pointer toward each other, and skip values you have just used so no triplet repeats.
The idea
Fix the first value of a triplet, and the other two must add up to its negative. Once the array is sorted, that pair can be found with two pointers closing in from both ends. Sorting also puts equal values next to each other, which makes repeats easy to skip.
Time O(n²)Extra space O(n) for the sorted copy
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Sort a copy in number order. The comparison function matters: without it, sort compares values as text and puts -2 after -1.
function threeSum(nums) { const sorted = [...nums].sort((a, b) => a - b); const out = []; for (let i = 0; i < sorted.length - 2; i++) { if (i > 0 && sorted[i] === sorted[i - 1]) continue; let left = i + 1; let right = sorted.length - 1; while (left < right) { const sum = sorted[i] + sorted[left] + sorted[right]; if (sum < 0) left++; else if (sum > 0) right--; else { out.push([sorted[i], sorted[left], sorted[right]]); while (left < right && sorted[left] === sorted[left + 1]) left++; while (left < right && sorted[right] === sorted[right - 1]) right--; left++; right--; } } } return out;}The trap
Three nested loops find every triplet of positions that adds up to zero, so an input with no repeated values passes. But the answer should list each triplet of values once. When a value appears more than once, the same triplet is found once for each mix of copies and listed several times. The loops also take O(n³) time.
function threeSum(nums) { const out = []; for (let i = 0; i < nums.length; i++) for (let j = i + 1; j < nums.length; j++) for (let k = j + 1; k < nums.length; k++) if (nums[i] + nums[j] + nums[k] === 0) out.push([nums[i], nums[j], nums[k]]); // repeats triplets return out;}