Problem 7 · Two Pointers & Sliding Window

3Sum

MediumClassic DSA & systems

01Problem

Return all unique triplets in nums that sum to zero.

02Key insight

Sort, fix one element, and run two-pointer Two Sum on the remainder. Sorting also makes de-duplication a matter of skipping equal neighbours.

03Solution

solution.pypython22 lines

def three_sum(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    n, result = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
                hi -= 1
    return result

Try it first.

TimeO(n^2)

SpaceO(1) extra (excluding sort/output)

tests.py · 3 passing

tests.pypython3 lines

assert three_sum([-1,0,1,2,-1,-4]) == [[-1,-1,2],[-1,0,1]]
assert three_sum([0,0,0,0]) == [[0,0,0]]
assert three_sum([0,1,1]) == []

04Staff-level follow-up

Generalise to k-sum? Recurse down to the 2-sum two-pointer base case for O(n^(k-1)); for k=4 a pair-sum hash map can trade memory for speed.