4Sum (LeetCode 18)

The problem

You get an integer array nums and a target. Return every unique quadruplet [a, b, c, d], using four different positions, whose values add up to target. No quadruplet of values may appear twice.

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

Each of the three lists sums to 0, and these are the only distinct ones.

How to think about it

Start with brute force. Four nested loops: O(n⁴), plus a set to remove repeated answers. Hopeless beyond tiny inputs.

The key insight: peel off one number at a time until it’s Two Sum II. 3Sum fixed one number and two-pointered the rest. 4Sum does the same thing with two fixed loops (i and j) and then a converging l/r scan for the last two numbers. Each level removes one power of n from the brute force, so you land at O(n³).

Duplicates have to be skipped at every level. After sorting, equal values are adjacent. Skip i if it repeats the previous i. Skip j if it repeats the previous j within the same i (that’s why the check is j > i + 1, not j > 0). After a match, step l and r past copies. With these three rules, every recorded quadruplet is unique.

Which pattern is this? Sort plus converging two pointers, generalised to k numbers. The tell is “all unique k-tuples with a target sum”. In an interview, mention that a recursive k-Sum reduces any k to Two Sum II.

Approach

1. Sort nums.
2. Loop i over the array; skip repeated values of nums[i].
3. Loop j from i + 1; skip repeated values of nums[j] after the first one for this i.
4. Set l = j + 1, r = n - 1, and compare the four-number sum with target, moving l up when too small and r down when too big.
5. On a match, record it, move both pointers, and skip duplicate values.
6. Return the list.

Solution

def four_sum(nums, target):
    nums.sort(); n = len(nums); res = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]: continue            # dup first number
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j-1]: continue    # dup second number
            l, r = j + 1, n - 1
            while l < r:
                s = nums[i] + nums[j] + nums[l] + nums[r]
                if s < target: l += 1
                elif s > target: r -= 1
                else:
                    res.append([nums[i], nums[j], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
    return res
# four_sum([1,0,-1,0,-2,2], 0) -> [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Dry run

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

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

Complexity

• Time: O(n³). Two nested loops over i and j, and an O(n) pointer scan inside.
• Space: O(1) extra apart from the output (and the sort’s internal memory).

Edge cases and pitfalls

• Fewer than four numbers: the loops don’t run; return [].
• All the same value ([2, 2, 2, 2, 2], target 8): returns [[2, 2, 2, 2]] once.
• The j duplicate check must be j > i + 1. Using j > 0 would skip the first j after each i whenever nums[j] == nums[i], missing answers like [0, 0, 0, 0].
• Overflow isn’t an issue in Python, but in Java or C++ the four-number sum can exceed 32 bits. Use a 64-bit type there.
• Breaking early on nums[i] > target is a bug when the target is negative; that 3Sum shortcut only works for target 0.

Related problems

• 3Sum (LeetCode 15): the same template with one fixed loop.
• Two Sum II – Input Array Is Sorted (LeetCode 167): the innermost scan.
• Combination Sum II (LeetCode 40): unique combinations with a target, solved by backtracking when the size isn’t fixed.