3Sum (LeetCode 15)

The problem

You get an integer array nums. Return every unique triplet [a, b, c] of values taken from three different positions such that a + b + c = 0. The same triplet of values must not appear twice in the answer.

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. There are two -1s in the input, but [-1, 0, 1] is listed only once.

How to think about it

Start with brute force. Three nested loops try every triplet: O(n³). You’d also need a set of sorted tuples to remove duplicate answers. Too slow for n in the thousands.

The key insight: fix one number, and the rest is Two Sum II. If you fix nums[i], you need two numbers from the rest that add up to -nums[i]. On a sorted array, that’s exactly the converging two-pointer scan from Two Sum II, which costs O(n). Doing it for each i gives O(n²).

Sorting also solves the duplicate problem. After sorting, equal values sit next to each other. So you can skip duplicates by position: skip i if it equals the previous i, and after recording a triplet, move l and r past any copies of the values you just used. Every triplet you record is then automatically unique, with no set needed. This duplicate handling is what interviewers actually watch.

A cheap early exit. Once nums[i] > 0, every number after it is also positive, so no triplet can reach zero. Stop.

Which pattern is this? Sort plus converging two pointers. The tell is “find all k-tuples with a target sum, no duplicates”.

Approach

1. Sort nums.
2. For each index i: skip it if nums[i] == nums[i-1]; stop if nums[i] > 0.
3. Set l = i + 1 and r = n - 1, and compute s = nums[i] + nums[l] + nums[r].
4. If s < 0, move l right; if s > 0, move r left.
5. If s == 0, record the triplet, move both pointers inward, then skip over repeated values on both sides.
6. Return all recorded triplets.

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   # same first value: skip
        if nums[i] > 0: break                          # can't reach zero any more
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l-1]: l += 1   # skip dup lefts
                while l < r and nums[r] == nums[r+1]: r -= 1   # skip dup rights
    return res
# three_sum([-1,0,1,2,-1,-4]) -> [[-1,-1,2],[-1,0,1]]

Dry run

After sorting: [-4, -1, -1, 0, 1, 2].

The result is [[-1, -1, 2], [-1, 0, 1]].

Complexity

• Time: O(n²). Sorting is O(n log n). Then each of the n values of i runs an O(n) two-pointer scan.
• Space: O(1) extra besides the output (Python’s sort uses O(n) internally, which is worth mentioning).

Edge cases and pitfalls

• Fewer than three numbers: the outer loop doesn’t run; return [].
• All zeros ([0, 0, 0, 0]): returns [[0, 0, 0]] exactly once, thanks to the skips.
• Skipping duplicates of i the wrong way. Compare with nums[i-1], not nums[i+1]. Comparing forward would skip the first -1 in [-1, -1, 2] and miss that triplet.
• Forgetting to skip after a match produces repeated triplets like [-2, 0, 2] twice for [-2, 0, 0, 2, 2].
• Using a set of tuples to deduplicate works but hides the real technique and adds overhead.

Related problems

• Two Sum II – Input Array Is Sorted (LeetCode 167): the inner loop of this solution, on its own.
• 3Sum Closest (LeetCode 16): the same shape, tracking the nearest sum instead of exact matches.
• 4Sum (LeetCode 18): add one more fixed loop and skip duplicates at every level.