Find every triple that sums to zero, with no repeats. Sort, fix one number, then close in from both ends with two pointers.
▼The problem
LeetCode 15 (Medium). Given a list of numbers, return every unique triplet [a, b, c] with a + b + c = 0.
Example (from LeetCode): [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]].
The solution
def three_sum(nums):
nums.sort()
out = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # same anchor
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 # skip repeats
return outTranscript
Three Sum. Given a list of numbers, find every group of three that adds up to zero. Each triplet counts only once.
Take minus one, zero, one, two, minus one, minus four. The answer is two triplets: minus one, minus one, two; and minus one, zero, one.
The naive way tries every group of three with nested loops: n cubed checks. And the same triplet can turn up twice, so you also have to remove duplicates.
The trick is to sort first. Pin one number as the anchor, put one hand just after it and the other at the far end. If the sum is below zero, move the left hand right. If it's above zero, move the right hand left. Every step rules out one number for good.
In code, sort, then loop over each anchor, skipping repeated anchors. Two pointers walk inward. On a match, record it and step past repeats, so no triplet comes out twice.
Sorted, the list is minus four, minus one, minus one, zero, one, two. Anchor minus four: every sum stays negative, so the left hand walks all the way. Anchor minus one: minus one, minus one, two makes zero. Record it. Then minus one, zero, two is too big, so the right hand moves. Minus one, zero, one. Record it. The second minus one is skipped. Anchor zero: one plus two is too big. Done.
Sorting costs n log n, and each anchor gets one inward sweep, so the time is n squared. Apart from the sort, the extra space is constant.
Sort, anchor, squeeze. That's Three Sum.