Practice: Three Sum
Sort, then two pointers.
Find every set of three numbers in a list that add up to zero, without repeating the same set twice. It's a famous step up from two sum. Pause. Could sorting, and two pointers, help?

- Three numbers that sum to zero
- No repeated sets
- Sort, then two pointers?
Fix one, search for two
First we sort. Then we fix one number at a time, and use two pointers on the rest to find a pair that cancels it out. Skipping numbers equal to the previous one prevents duplicate answers. Run it. Two triplets, minus one, minus one, two, and minus one, zero, one.
def three_sum(nums):
nums, out = sorted(nums), []
for i in range(len(nums) - 2):
if i and nums[i] == nums[i - 1]: continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0: lo += 1
elif s > 0: hi -= 1
else:
out.append([nums[i], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]: lo += 1
return out
print(three_sum([-1, 0, 1, 2, -1, -4]))[[-1, -1, 2], [-1, 0, 1]]
Building on two sum
Three sum is two sum, with one number fixed. Sorting costs O of N log N, and the loop with two pointers costs O of N squared, so that's the total. Interviewers love this kind of question, because it rewards seeing an old problem inside a new one.
| key | value |
|---|---|
| Sort | O(n log n) |
| Fix one | outer loop |
| Two pointers | inner search |
| Total | O(n²) |
Summary
Sort, fix one number, and use two pointers to find the other two, skipping duplicates. Next, the best stretch of a list, with Kadane's algorithm.
Key takeaways- Sort first
- Fix one, two pointers for the rest
- Skip duplicates