Coding · Two pointers
3Sum
- Reported once
- Medium
- SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Given an array of integers, find every distinct triple of values that adds up to zero, using three different positions in the array. List each triple in ascending order and the triples in ascending order too, so the answer is unique, and never list the same triple twice even if its values occur several times. For example, [-1,0,1,2,-1,-4] gives [[-1,-1,2],[-1,0,1]]. The array has up to 3,000 numbers.
Restated in our own words, not a quote from Swiggy or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: must the three numbers come from three different positions, while equal values at different positions are fine, as in [-1,-1,2]? Should each distinct triple appear once? Can I sort or copy the input? What do I return if nothing matches, or if the array has fewer than three numbers? How big can it be?
I will assume three different positions, each distinct value-triple reported once, sorting a copy is fine, and an empty list is the answer when no triple exists. I will return each triple in ascending order, with the triples in ascending order, so the output is deterministic.
Brute force
Say the obvious answer and why it is too slow.
The direct approach is three nested loops over positions i < j < k, checking whether the sum is zero, and putting each sorted triple in a set to remove duplicates.
That is O(n³): with 3,000 numbers there are about 4.5 billion triples to check, which is far beyond a second or two. A middle path fixes one number and uses a hash set to find the other two in one pass, giving O(n²), but removing duplicate triples with a set of strings is clumsy and memory hungry. Sorting makes both the search and the duplicate handling much cleaner.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n³)
- Time
- O(n²)
- Space
- O(n) with a sorted copy
Sort a copy of the array. Then fix the smallest number of the triple at position i and look for two numbers to its right whose sum is -sorted[i]. Use two pointers: left starts at i + 1 and right at the end.
Look at the sum of the three. If it is below zero, the number at left is too small to work with anything at or left of right, so I can discard left and move it up. If it is above zero, the number at right is too big for anything at or right of left, so I discard right and move it down. If it is exactly zero, I record the triple and move both pointers inward. This is the invariant: no valid pair for this i uses a position outside [left, right]. Each step removes one position, so one i costs O(n).
Duplicates are handled by order. Skip an i whose value equals the previous one, because the earlier i already explored every pair. After recording a triple, move left and right past values equal to the ones just used. Because the array is sorted, equal values sit next to each other, so these skips are enough to guarantee each triple appears once. If sorted[i] is already positive, nothing to its right can bring the sum down to zero, so I stop.
The pattern is sort, then fix one and sweep two pointers. Total time is O(n²), dominated by n sweeps.
Walk it through
A dry run on the example, step by step.
| step | i (value) | left (value) | right (value) | sum | move |
|---|---|---|---|---|---|
| 1 | 0 (-4) | 1 (-1) | 5 (2) | -3 | left++ |
| 2 | 0 (-4) | 2 (-1) | 5 (2) | -3 | left++ |
| 3 | 0 (-4) | 3 (0) | 5 (2) | -2 | left++ |
| 4 | 0 (-4) | 4 (1) | 5 (2) | -1 | left++, meet |
| 5 | 1 (-1) | 2 (-1) | 5 (2) | 0 | record [-1,-1,2] |
| 6 | 1 (-1) | 3 (0) | 4 (1) | 0 | record [-1,0,1] |
| 7 | 2 (-1) | - | - | - | skip duplicate i |
| 8 | 3 (0) | 4 (1) | 5 (2) | 3 | right--, meet |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take [-1,0,1,2,-1,-4]. Sorted, it is [-4,-1,-1,0,1,2].
With i at -4, the pair sums are too small at each step (-3, -3, -2, -1), so left moves right until it meets right. Next i is the first -1: left at the second -1 and right at 2 give sum 0, so I record [-1,-1,2]; then left at 0 and right at 1 also sum to 0, so I record [-1,0,1]. The next i is also -1, a duplicate of the previous one, so it is skipped. With i at 0, left at 1 and right at 2 give sum 3, too big, so right moves left and the pointers meet.
The trace table shows every step. The answer is [[-1,-1,2],[-1,0,1]].
The code
Runnable JavaScript, checked against test cases.
function threeSum(nums) {
const sorted = [...nums].sort((a, b) => a - b);
const triples = [];
for (let i = 0; i < sorted.length - 2; i++) {
if (sorted[i] > 0) break;
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 {
triples.push([sorted[i], sorted[left], sorted[right]]);
left++;
right--;
while (left < right && sorted[left] === sorted[left - 1]) left++;
while (left < right && sorted[right] === sorted[right + 1]) right--;
}
}
}
return triples;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Fewer than three numbers: the loop bound i < n - 2 never runs, so the result is empty. An array of all zeros, such as [0,0,0,0], gives exactly one triple, because after recording it the pointer skips remove the remaining equal values and the repeated i is skipped.
All positive or all negative numbers give an empty list; the break on a positive first number handles the first case quickly. Mixed duplicates like [-1,-1,-1,2,2] yield [-1,-1,2] once. The sort uses a numeric comparator, since the default JavaScript sort compares text and would put 10 before 2. I sort a copy, so the caller's array is left untouched.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve 3Sum Closest, where the sum only has to be nearest to a target?
- Can you do it with a hash set instead of sorting, and what does duplicate removal cost you?
- How does the approach extend to 4Sum, and what is its time?
- What changes if you must count the triples instead of listing them?
Where candidates slip
The mistakes this problem punishes.
The most frequent bug is duplicate triples in the output, from forgetting to skip repeated values for i, or for left and right after a hit. A second is skipping duplicates before checking, which can throw away the legitimate [-1,-1,2] pair: the skip for i must compare with the previous i, not the next one.
Other slips: sorting with the default comparator so negative numbers and multi-digit numbers order wrongly; moving neither pointer after a hit, which loops forever, or only one of them, which repeats the same triple; letting left and right cross while the duplicate skip runs, so the skip loops need the left < right guard; and picking the same position twice.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.