3Sum Without Duplicates: Sort, Fix One, Two Pointers

3Sum asks for all unique triplets that sum to zero. The algorithm is short; the part interviewers watch is how you avoid duplicate triplets without a hash set of tuples.

Sort first

Sorting costs O(n log n), which is cheaper than the O(n^2) scan that follows, and it unlocks two things: two pointers, and skipping equal neighbours to remove duplicates.

Fix one number, then two pointers

For each index i, look for two numbers in nums[i+1:] that sum to -nums[i]. Move lo up when the sum is too small and hi down when it is too large.

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

Where the duplicates go

Two skips handle everything: skip a fixed value equal to the previous fixed value, and after a match, advance lo past equal values. The early break when nums[i] > 0 is a cheap optimisation worth mentioning.

Follow-ups

3Sum Closest uses the same loop and tracks the best distance. 4Sum adds one more fixed index and generalises to kSum by recursion down to the two-pointer base case. Total time for 3Sum is O(n^2) with O(1) extra space besides the output.

If you practise explaining patterns like this out loud, an AI interview assistant can prompt you when you skip a step. Disclosure: I help build Linkjob AI.