4Sum

Difficulty: Medium Source: NeetCode

Problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that a, b, c, d are distinct indices and nums[a] + nums[b] + nums[c] + nums[d] == target.

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

Example 2: Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]

Constraints:

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

Prerequisites

Before attempting this problem, you should be comfortable with:

• 3Sum — sort + fix one element + two-pointer inner search
• Two Pointers — extending the 3Sum pattern by adding one more fixed element
• Duplicate Skipping — careful index advancement to avoid repeated quadruplets

1. Brute Force

Intuition

Enumerate every combination of four distinct indices, check if their values sum to target, and collect unique quadruplets. Sorting each found quadruplet and storing them in a set handles deduplication. Works, but four nested loops make it unusably slow for any real input.

Algorithm

1. Initialize result as a set.
2. Use four nested loops over indices a < b < c < d.
3. If the four values sum to target, add the sorted tuple to result.
4. Convert result to a list of lists and return.

Solution

def fourSum(nums, target):
    result = set()
    n = len(nums)
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                for d in range(c + 1, n):
                    if nums[a] + nums[b] + nums[c] + nums[d] == target:
                        result.add(tuple(sorted([nums[a], nums[b], nums[c], nums[d]])))
    return [list(t) for t in result]


print(fourSum([1, 0, -1, 0, -2, 2], 0))  # [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
print(fourSum([2, 2, 2, 2, 2], 8))        # [[2, 2, 2, 2]]

Complexity

• Time: O(n⁴)
• Space: O(k) where k is the number of unique quadruplets

2. Sort + Two Fixed Pointers + Two Pointers

Intuition

4Sum is just 3Sum with one more outer loop. Sort the array, then fix the first element with index i and the second with index j. For the remaining two elements, run the familiar two-pointer search on nums[j+1 .. n-1]. The duplicate-skipping logic from 3Sum applies independently to i, j, and both inner pointers.

Algorithm

1. Sort nums.
2. For i from 0 to n - 4:
   • Skip if i > 0 and nums[i] == nums[i - 1].
   • For j from i + 1 to n - 3:
     • Skip if j > i + 1 and nums[j] == nums[j - 1].
     • Set left = j + 1, right = n - 1.
     • While left < right:
       • Compute total = nums[i] + nums[j] + nums[left] + nums[right].
       • If equal to target: record quadruplet, advance left/retreat right, skip duplicates.
       • If total < target: increment left.
       • If total > target: decrement right.
3. Return result.

Solution

def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1

    return result


print(fourSum([1, 0, -1, 0, -2, 2], 0))  # [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
print(fourSum([2, 2, 2, 2, 2], 8))        # [[2, 2, 2, 2]]
print(fourSum([0, 0, 0, 0], 0))           # [[0, 0, 0, 0]]

Complexity

• Time: O(n³)
• Space: O(1) extra (output list not counted)

Common Pitfalls

Inner duplicate skip guard for j. The guard must be j > i + 1 (not j > 0) — otherwise you skip the very first j for each i.

Integer overflow with large values. The problem allows values up to 10^9 and target up to 10^9, so the sum of four numbers can reach 4 * 10^9. Python handles arbitrary-precision integers natively, but in languages like C++ or Java you’d need long to avoid overflow.

Thinking this generalizes to O(n²). 4Sum is inherently O(n³) — we have two fixed outer loops (O(n²)) and a two-pointer inner loop (O(n)). There is no known sub-cubic solution for the general case.