Appearance
4.5.3 — 3Sum
LeetCode 15 · Medium · ★ Blind 75
The problem
You are given an unsorted list of numbers called nums. Find every different group of three numbers in it that adds up to zero. Each group must use three different positions. The list can contain repeated values, but the answer must not contain the same group twice.
nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
nums = [0, 1, 1] → []
nums = [0, 0, 0] → [[0, 0, 0]]Look at the first example. There are two −1s in the list, and either one could pair with 0 and 1 to make [-1, 0, 1]. But that group appears only once in the answer. The "no repeated groups" rule is where all the difficulty is, not the adding up.
The list has between 3 and 3,000 numbers.
What the problem is really asking
Three numbers add to zero exactly when the first one equals minus the sum of the other two. So if you fix the first number, say −4, you need two more numbers that add up to 4. That is the problem from the last page, 4.5.2 Two Sum II.
So the question becomes: for each possible first number, find every pair after it that adds to its negative, without ever producing the same group twice.
The brute force, and where it wastes work
Try every group of three positions. To avoid repeats, sort each group and store it in a set.
python
def threeSum(nums):
n = len(nums)
found = set()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
return [list(t) for t in found]Three loops inside each other try about \frac{n^3}{6} groups. For 3,000 numbers that is 4.5 billion groups. Far too slow.
The waste in one sentence: for each fixed pair i, j, the innermost loop searches the whole rest of the list for one known value, and the sorted-tuple set is a clumsy way of cleaning up repeats that a sorted list would never create.
The idea
Sort the list first. Sorting n numbers takes O(n \log n) time. That is cheap compared with the O(n^2) solution we are heading for, and it gives us two things.
- Two pointers work. Two Sum II needed a sorted list, and now we have one.
- Equal values sit next to each other. So skipping a repeat is as simple as asking "is this the same as the number just before it?"
Then the plan is:
- Fix the first number,
nums[i], one position at a time. - On everything to the right of
i, run Two Sum II with two pointers, looking for pairs that add to-nums[i]. - Skip any value that would only rebuild a group we already found.
Think of a teacher grouping students whose scores add to zero. Picking three students at random is overwhelming. So the teacher lines everyone up by score, picks the first student, and says, "your score is −5, so I need two more whose scores add to +5." The teacher then uses the see-saw method from the last page on the rest of the line. A three-person problem has become a two-person problem the teacher already knows how to solve.
The solution
python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # (1)
result = []
for i in range(len(nums) - 2): # (2)
if nums[i] > 0: # (3)
break
if i > 0 and nums[i] == nums[i - 1]: # (4)
continue
l, r = i + 1, len(nums) - 1 # (5)
while l < r:
total = nums[i] + nums[l] + nums[r] # (6)
if total < 0: # (7)
l += 1
elif total > 0:
r -= 1
else: # (8)
result.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]: # (9)
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
return resultts
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b); // (1)
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i++) { // (2)
if (nums[i] > 0) break; // (3)
if (i > 0 && nums[i] === nums[i - 1]) continue; // (4)
let l = i + 1, r = nums.length - 1; // (5)
while (l < r) {
const total = nums[i] + nums[l] + nums[r]; // (6)
if (total < 0) l++; // (7)
else if (total > 0) r--;
else { // (8)
result.push([nums[i], nums[l], nums[r]]);
l++;
r--;
while (l < r && nums[l] === nums[l - 1]) l++; // (9)
while (l < r && nums[r] === nums[r + 1]) r--;
}
}
}
return result;
}Line by line
(1) Sort. In Python, nums.sort() sorts numbers by value. In TypeScript you must write nums.sort((a, b) => a - b). Without the little function, JavaScript sorts as text, comparing the first character first. So [10, 9] would stay [10, 9], because the text "1" comes before the text "9". The function (a, b) => a - b tells it to compare by value instead.
(2) Fix the first number. i goes from 0 up to the third-from-last position. We stop there because we need room for two more numbers after i.
(3) Stop once the fixed number is positive. The list is sorted, so if nums[i] is above zero, every number after it is also above zero. Three positive numbers can never add to zero. So we can stop the whole search. The answer would still be correct without this line, but it saves time.
(4) Skip a repeated first number. If nums[i] equals nums[i - 1], then every group starting with this value was already found when we fixed nums[i - 1]. Running again would only find the same groups a second time. The check i > 0 protects position 0, which has no number before it.
(5) Two pointers on the rest. l starts just after i, and r starts at the end.
(6) Add up the three numbers.
(7) Move a pointer, exactly as in Two Sum II. If the sum is below zero, we need bigger numbers, so l moves right. If it is above zero, r moves left.
(8) A match. Record the group. Then move both pointers inward, because both of those numbers have now been used with this nums[i].
(9) Skip repeated second and third numbers. After moving, l might land on the same value it just left. For example, after using a −1, the next number might also be −1. Using it would rebuild the same group. So we keep moving l while its value equals the one just before it. We do the mirror check for r, comparing with the value just after it.
This skip only appears inside the match branch, and that is on purpose. A repeated group can only be produced when we record a group. When the sum is simply too big or too small, moving one step is already correct, and the normal pointer moves will pass over repeats on their own.
Trace
Take nums = [-1, 0, 1, 2, -1, -4]. After sorting, it is [-4, -1, -1, 0, 1, 2], with positions 0 to 5.
i | Fixed | Pointer steps | Groups found |
|---|---|---|---|
| 0 | −4 | needs a pair adding to 4. The biggest pair is 1 + 2 = 3, so l keeps moving right until it meets r. | none |
| 1 | −1 | l=2 (−1), r=5 (2): sum 0 → found. Move to l=3 (0), r=4 (1): sum 0 → found. Move, pointers cross. | [-1, -1, 2], [-1, 0, 1] |
| 2 | −1 | same as nums[1], so line (4) skips it | — |
| 3 | 0 | l=4 (1), r=5 (2): sum 3, too big, r moves left, pointers meet | none |
Without line (4), i = 2 would fix the second −1 and find [-1, 0, 1] again, and the answer would contain it twice.
Complexity, derived
Time. Sorting takes O(n \log n).
The outer loop runs up to n times. For each i, the two pointers start at opposite ends of the rest of the list and move toward each other. Each step moves at least one pointer, and the skips in line (9) only move them further in the same direction. So for one i, the pointers take at most n steps in total. That is O(n) per i, and O(n) \times n = O(n^2) for the whole loop.
Adding the sort: O(n \log n) + O(n^2). For large n, n^2 grows much faster than n \log n, so the total is O(n^2).
Space. Apart from the answer, we only keep a few pointer variables, so the extra memory is O(1). One honest footnote: Python's built-in sort can use up to O(n) temporary memory while it works. Mention this if the interviewer is strict about space.
Edge cases
- All zeros, such as
[0, 0, 0, 0]. The firstifinds[0, 0, 0]. Line (9) skips the other zeros for the pointers, and line (4) skips the other zeros fori. The answer is exactly[[0, 0, 0]]. - No group works, such as
[1, 2, 3]. Line (3) stops at once, because the first number is already positive. The answer is[]. - Exactly three numbers. The outer loop runs once.
Changing the caller's list
nums.sort() changes the order of the list that was passed in. On a coding judge that does not matter. In real code it can cause a hard-to-find bug, because another part of the program might still be reading that list and not expect it to have moved.
If the list belongs to someone else, use sorted(nums) in Python, or [...nums].sort(...) in TypeScript. Both make a sorted copy and leave the original alone. The copy costs O(n) extra memory.
Variations you will meet
- 3Sum Closest. Find the three numbers whose sum is closest to a target. Same loops, but you remember the closest sum seen. There is no repeat-skipping at all, which shows how much of 3Sum was really about repeats.
- 4Sum. Add one more outer loop, with the same repeat-skip at each level. That is O(n^3).
- 3Sum Smaller. Count the groups whose sum is below a target. When
nums[i] + nums[l] + nums[r]is below the target, then everyrbetweenl + 1and the currentralso works with thisl, because those numbers are even smaller. So you addr - lto the count in one step and movel. Counting a whole range at once is the useful idea there.
The general lesson: to solve a k-number sum, fix one number and solve the (k − 1)-number sum on the rest. The smallest case, two numbers, is two pointers.
What the interviewer will push on
"Why sort?" Give both reasons. Sorting makes two pointers possible, and it puts equal values side by side, so repeats are cheap to skip.
"Where exactly do you skip repeats, and why there?" Line (4) for the fixed number, and line (9) inside the match branch for the pair. Repeated groups can only appear when you record a group.
"Could you use a hash set instead of two pointers?" Yes. Fix two numbers and look up the third in a set. That is also O(n^2) time, but it uses O(n) memory, and removing repeated groups gets messy, because you end up sorting each group to use it as a key.
"Your sort changes the input list." Agree, and offer to sort a copy instead.
One thing to volunteer: say that the "no repeated groups" rule is the hard part of this problem, not the arithmetic. That observation shows you have actually written it.
Next: 4.5.4 Container With Most Water. Two pointers again, but now the rule for which pointer moves comes from geometry rather than from sorting.