3Sum

3Sum is the classic next step after Two Sum. Instead of finding one pair, you find every unique trio that adds up to zero. The winning idea is to sort the array first, then fix one number and use two pointers to find the matching pair fast.

The idea

The brute force tries every trio with three nested loops — that is O(n³), far too slow. We can do much better.

First, sort the array. Now walk a fixed index i from left to right. For each nums[i], the other two numbers must sum to -nums[i]. Finding a pair with a known sum in a sorted array is the two-pointer trick: put lo just after i and hi at the end.

• If nums[lo] + nums[hi] is too small, move lo right to make the sum bigger.
• If it is too big, move hi left to make the sum smaller.
• If it is exactly the target, record the triplet and move both pointers inward.

Sorting is what makes this work: it turns "search the whole array" into "nudge a pointer in the right direction."

The other job is avoiding duplicates. Because the array is sorted, equal numbers sit next to each other. So we skip a fixed i if it equals the previous one, and after recording a hit we skip equal lo/hi values too. That keeps every triplet unique without a separate dedup pass.

Walk through it

Step through the animation. The array is shown already sorted: [-4, -1, -1, 0, 1, 2]. The pointer i fixes one number; lo and hi close in from both sides. Watch the fixed value -1 (at i = 1): the sweep finds two triplets, [-1, -1, 2] and [-1, 0, 1]. Then the second -1 is skipped as a duplicate, and 0 finds nothing because its smallest pair already overshoots zero.

Pseudocode

sort nums
result = empty list
for i from 0 to n - 3:
    if i > 0 and nums[i] == nums[i - 1]:
        continue                       # skip a duplicate fixed value
    lo = i + 1
    hi = n - 1
    while lo < hi:
        s = nums[i] + nums[lo] + nums[hi]
        if s == 0:
            record [nums[i], nums[lo], nums[hi]]
            move lo right, move hi left
            skip lo/hi over equal values   # avoid duplicate triplets
        else if s < 0:
            move lo right                  # sum too small
        else:
            move hi left                   # sum too big
return result

The outer loop fixes one number; the inner two-pointer loop scans the rest in linear time.

The Python solution

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 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:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return res

• nums.sort() is what unlocks the two-pointer move — without it, nudging lo/hi would be meaningless.
• The outer loop fixes nums[i]; the if i > 0 and nums[i] == nums[i - 1] guard skips a repeated fixed value so we never emit the same triplet twice.
• s = nums[i] + nums[lo] + nums[hi] is the running sum of the current trio.
• When s == 0 we record the triplet and move both pointers inward. When s < 0 the sum is too small so lo goes right; when s > 0 it is too big so hi goes left.
• A production version also skips equal lo/hi values right after a hit — the animation leaves that detail out to keep the line mapping simple, but the prose dedup guard on i is the key idea.

Complexity

Sorting costs O(n log n), which is dwarfed by the O(n²) sweep. The extra space is O(1) beyond the output list (the sort is in place). The big win is O(n³) → O(n²) — the same "sort, then two pointers" pattern that powers 3Sum Closest, 4Sum, and many container/interval problems.

When this pattern shows up

Practice