Three Sum and Avoiding Duplicates

24 min · Intermediate

Three sum is the classic next step after pair sum. A triple search sounds like three loops, but sorting plus one loop and two pointers brings it from O(n cubed) to O(n squared).

Sort, fix one value, then two pointers

Three sum asks for all unique triples in a list that add up to a target, usually zero. Sort the list, fix one value, and search the pair on the right with two pointers in O(n squared) time.

Find three values that add up to zero. Sort the list, fix the first value, and the rest is a pair-sum problem on what remains to the right. That turns three loops into one loop plus two pointers.

Example 1 · Brute force with three loops

Python

1nums = [-1, 0, 1, 2, -1, -4]2found = set()3for i in range(len(nums)):4    for j in range(i + 1, len(nums)):5        for k in range(j + 1, len(nums)):6            if nums[i] + nums[j] + nums[k] == 0:7                found.add(tuple(sorted((nums[i], nums[j], nums[k]))))8print(sorted(found))

Output

[(-1, -1, 2), (-1, 0, 1)]

What this code does

Three nested loops try every triple, so the time is O(n cubed). A set of sorted tuples removes repeats.
It is fine for six values and far too slow for thousands.

Example 2 · Sort, fix one value, then two pointers

Python

1def three_sum_set(nums):2    nums = sorted(nums)3    found = set()4    for i in range(len(nums) - 2):5        left, right = i + 1, len(nums) - 16        while left < right:7            total = nums[i] + nums[left] + nums[right]8            if total < 0:9                left += 110            elif total > 0:11                right -= 112            else:13                found.add((nums[i], nums[left], nums[right]))14                left += 115                right -= 116    return sorted(found)17
18
19print(three_sum_set([-1, 0, 1, 2, -1, -4]))

Output

[(-1, -1, 2), (-1, 0, 1)]

What this code does

A set of tuples removes repeated triples, but it uses extra space and hides the real work.
The next section avoids repeats by skipping equal values.

Skip duplicates

Equal values next to each other give the same triple again. Skip the next outer value if it equals the one before, and after a match move both inner pointers past equal values.

Example 3 · The pair search inside

Python

1nums = sorted([-1, 0, 1, 2, -1, -4])2i = 03left, right = i + 1, len(nums) - 14while left < right:5    total = nums[i] + nums[left] + nums[right]6    print(nums[i], nums[left], nums[right], total)7    if total < 0:8        left += 19    elif total > 0:10        right -= 111    else:12        break

Output

-4 -1 2 -3
-4 -1 2 -3
-4 0 2 -2
-4 1 2 -1

What this code does

With the first value fixed at -4, the pair search can never reach zero.
Each line is one round of the inner loop.

Example 4 · Unique triples

Python

1def three_sum(nums):2    nums = sorted(nums)3    result = []4    for i in range(len(nums) - 2):5        if i > 0 and nums[i] == nums[i - 1]:6            continue7        left, right = i + 1, len(nums) - 18        while left < right:9            total = nums[i] + nums[left] + nums[right]10            if total < 0:11                left += 112            elif total > 0:13                right -= 114            else:15                result.append([nums[i], nums[left], nums[right]])16                left += 117                right -= 118                while left < right and nums[left] == nums[left - 1]:19                    left += 120                while left < right and nums[right] == nums[right + 1]:21                    right -= 122    return result23
24
25print(three_sum([-1, 0, 1, 2, -1, -4]))26print(three_sum([0, 0, 0, 0]))

Output

[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]

What this code does

The first call returns two triples, each once, even though -1 appears twice.
The second call shows that four zeros give one triple, not four.
Sorting makes equal values neighbours, so nums[i] == nums[i - 1] is enough to spot repeats.
Results come out in sorted order.

Stop early and count the cost

Once the fixed value is above zero, every value to its right is also above zero, so no triple can sum to zero. The loop can stop there.

Example 5 · Duplicates in the middle

Python

1def three_sum(nums):2    nums = sorted(nums)3    result = []4    for i in range(len(nums) - 2):5        if i > 0 and nums[i] == nums[i - 1]:6            continue7        left, right = i + 1, len(nums) - 18        while left < right:9            total = nums[i] + nums[left] + nums[right]10            if total < 0:11                left += 112            elif total > 0:13                right -= 114            else:15                result.append([nums[i], nums[left], nums[right]])16                left += 117                right -= 118                while left < right and nums[left] == nums[left - 1]:19                    left += 120                while left < right and nums[right] == nums[right + 1]:21                    right -= 122    return result23
24
25print(three_sum([-2, 0, 0, 2, 2]))26print(three_sum([1, 2, 3]))

Output

[[-2, 0, 2]]
[]

What this code does

Two zeros and two 2s still give a single triple, -2 + 0 + 2.
No triple sums to zero in the second call, so the result is an empty list.

Example 6 · Stop early and count the cost

Python

1def three_sum_fast(nums):2    nums = sorted(nums)3    result = []4    for i in range(len(nums) - 2):5        if nums[i] > 0:6            break7        if i > 0 and nums[i] == nums[i - 1]:8            continue9        left, right = i + 1, len(nums) - 110        while left < right:11            total = nums[i] + nums[left] + nums[right]12            if total < 0:13                left += 114            elif total > 0:15                right -= 116            else:17                result.append([nums[i], nums[left], nums[right]])18                left += 119                right -= 120                while left < right and nums[left] == nums[left - 1]:21                    left += 122    return result23
24
25print(three_sum_fast([3, -2, 1, 0, -1, 2, -3]))

Output

[[-3, 0, 3], [-3, 1, 2], [-2, -1, 3], [-2, 0, 2], [-1, 0, 1]]

What this code does

Sorting costs O(n log n) and the main loop costs O(n squared), so the total is O(n squared).
Extra space is O(1) besides the result.

Any target, not only zero

For a target other than zero, compare the three-value total with the target instead of zero. The rest of the code is the same, so this one function covers many problems.

Example 7 · Three sum closest

Python

1def closest_sum(nums, target):2    nums = sorted(nums)3    best = nums[0] + nums[1] + nums[2]4    for i in range(len(nums) - 2):5        left, right = i + 1, len(nums) - 16        while left < right:7            total = nums[i] + nums[left] + nums[right]8            if abs(total - target) < abs(best - target):9                best = total10            if total < target:11                left += 112            elif total > target:13                right -= 114            else:15                return total16    return best17
18
19print(closest_sum([-1, 2, 1, -4], 1))

Output

What this code does

Same fix-one-then-search structure, but the goal is the smallest distance to the target.
An exact hit returns at once. Time is O(n squared).

Example 8 · Any target, not only zero

Python

1def triples_with_sum(nums, target):2    nums = sorted(nums)3    result = []4    for i in range(len(nums) - 2):5        if i > 0 and nums[i] == nums[i - 1]:6            continue7        left, right = i + 1, len(nums) - 18        while left < right:9            total = nums[i] + nums[left] + nums[right]10            if total < target:11                left += 112            elif total > target:13                right -= 114            else:15                result.append([nums[i], nums[left], nums[right]])16                left += 117                right -= 118                while left < right and nums[left] == nums[left - 1]:19                    left += 120    return result21
22
23print(triples_with_sum([5, 1, 3, 2, 4, 6], 10))

Output

[[1, 3, 6], [1, 4, 5], [2, 3, 5]]

What this code does

Replace the 0 in the comparisons with target.
The skipping rules keep the answers unique.

Next step

Check your understanding

11 quick questions

Sort, fix one value, then two pointers

Three sum asks for all unique triples in a list that add up to a target, usually zero. Sort the list, fix one value, and search the pair on the right with two pointers in O(n squared) time.

Find three values that add up to zero. Sort the list, fix the first value, and the rest is a pair-sum problem on what remains to the right. That turns three loops into one loop plus two pointers.

1nums = [-1, 0, 1, 2, -1, -4]2found = set()3for i in range(len(nums)):4 for j in range(i + 1, len(nums)):5 for k in range(j + 1, len(nums)):6 if nums[i] + nums[j] + nums[k] == 0:7 found.add(tuple(sorted((nums[i], nums[j], nums[k]))))8print(sorted(found))

1def three_sum_set(nums):2 nums = sorted(nums)3 found = set()4 for i in range(len(nums) - 2):5 left, right = i + 1, len(nums) - 16 while left < right:7 total = nums[i] + nums[left] + nums[right]8 if total < 0:9 left += 110 elif total > 0:11 right -= 112 else:13 found.add((nums[i], nums[left], nums[right]))14 left += 115 right -= 116 return sorted(found)17 18 19print(three_sum_set([-1, 0, 1, 2, -1, -4]))

1nums = sorted([-1, 0, 1, 2, -1, -4])2i = 03left, right = i + 1, len(nums) - 14while left < right:5 total = nums[i] + nums[left] + nums[right]6 print(nums[i], nums[left], nums[right], total)7 if total < 0:8 left += 19 elif total > 0:10 right -= 111 else:12 break

1def three_sum(nums):2 nums = sorted(nums)3 result = []4 for i in range(len(nums) - 2):5 if i > 0 and nums[i] == nums[i - 1]:6 continue7 left, right = i + 1, len(nums) - 18 while left < right:9 total = nums[i] + nums[left] + nums[right]10 if total < 0:11 left += 112 elif total > 0:13 right -= 114 else:15 result.append([nums[i], nums[left], nums[right]])16 left += 117 right -= 118 while left < right and nums[left] == nums[left - 1]:19 left += 120 while left < right and nums[right] == nums[right + 1]:21 right -= 122 return result23 24 25print(three_sum([-1, 0, 1, 2, -1, -4]))26print(three_sum([0, 0, 0, 0]))

1def three_sum_fast(nums):2 nums = sorted(nums)3 result = []4 for i in range(len(nums) - 2):5 if nums[i] > 0:6 break7 if i > 0 and nums[i] == nums[i - 1]:8 continue9 left, right = i + 1, len(nums) - 110 while left < right:11 total = nums[i] + nums[left] + nums[right]12 if total < 0:13 left += 114 elif total > 0:15 right -= 116 else:17 result.append([nums[i], nums[left], nums[right]])18 left += 119 right -= 120 while left < right and nums[left] == nums[left - 1]:21 left += 122 return result23 24 25print(three_sum_fast([3, -2, 1, 0, -1, 2, -3]))

1def closest_sum(nums, target):2 nums = sorted(nums)3 best = nums[0] + nums[1] + nums[2]4 for i in range(len(nums) - 2):5 left, right = i + 1, len(nums) - 16 while left < right:7 total = nums[i] + nums[left] + nums[right]8 if abs(total - target) < abs(best - target):9 best = total10 if total < target:11 left += 112 elif total > target:13 right -= 114 else:15 return total16 return best17 18 19print(closest_sum([-1, 2, 1, -4], 1))

1def triples_with_sum(nums, target):2 nums = sorted(nums)3 result = []4 for i in range(len(nums) - 2):5 if i > 0 and nums[i] == nums[i - 1]:6 continue7 left, right = i + 1, len(nums) - 18 while left < right:9 total = nums[i] + nums[left] + nums[right]10 if total < target:11 left += 112 elif total > target:13 right -= 114 else:15 result.append([nums[i], nums[left], nums[right]])16 left += 117 right -= 118 while left < right and nums[left] == nums[left - 1]:19 left += 120 return result21 22 23print(triples_with_sum([5, 1, 3, 2, 4, 6], 10))