3Sum

Interview Prep

StandardTwo Pointersarraystwo-pointerssorting

The problem

Given an integer array, return all unique triples (a, b, c) in the array such that a + b + c = 0. "Unique" means no duplicate triples even if duplicate values exist.

Pattern: sort + two-pointer extension of Two Sum

Two Sum (hashmap) solves the 2-element version in O(n). The natural generalization fixes one element and runs Two Sum on the rest — except a hashmap version of that is hard to deduplicate. So: sort the array, then for each anchor nums[i], run a two-pointer sweep on the suffix for the complement −nums[i]. Sorting makes deduplication trivial: identical adjacent values become a single "skip if same as previous" check.

The two-pointer trick on a sorted array: if the current pair sum is too small, advance the low pointer (only way to increase). If too large, retract the high pointer. O(n) per anchor, and n anchors, gives O(n²) total.

Brute force: every triple

def three_sum_brute(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    seen = set()
    out = []
    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:
                    key = tuple(sorted([nums[i], nums[j], nums[k]]))
                    if key not in seen:
                        seen.add(key)
                        out.append(list(key))
    return out

Optimal: sort + two pointers

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    out = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0: break                        # smallest > 0, no triple can sum to 0
        if i > 0 and nums[i] == nums[i - 1]: continue # skip duplicate anchors
        target = -nums[i]
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1; hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]: lo += 1   # skip dup
                while lo < hi and nums[hi] == nums[hi + 1]: hi -= 1
    return out

Trace

nums = [-1, 0, 1, 2, -1, -4]
sorted: [-4, -1, -1, 0, 1, 2]

i=0, anchor=-4, target=4: two-sum on [-1,-1,0,1,2] for 4. max pair = 1+2 = 3. No hit.
i=1, anchor=-1, target=1: two-sum on [-1,0,1,2].
    lo=-1, hi=2 -> sum 1, hit! append [-1, -1, 2]. lo++, hi--.
    lo=0,  hi=1 -> sum 1, hit! append [-1, 0, 1].  lo++, hi--.  lo>=hi, stop.
i=2, anchor=-1, same as prev — skip.
i=3, anchor=0, target=0: two-sum on [1,2]. min pair = 3 > 0. No hit.

result = [[-1, -1, 2], [-1, 0, 1]]

Complexity

Variations worth knowing