Four Sum

The Problem

Given an integer array arr and an integer target, find all unique quadruplets [a, b, c, d] such that a + b + c + d = target. The solution set must not contain duplicate quadruplets.

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

Examples

Example 1

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

Example 2

Input:  arr = [2, 2, 2, 2, 2],  target = 8
Output: [[2, 2, 2, 2]]
Explanation: All elements are 2; only one unique quadruplet exists.

Example 3

Input:  arr = [1, 2, 3, 4],  target = 100
Output: []
Explanation: No quadruplet sums to 100.

Example 4

Input:  arr = [0, 0, 0, 0],  target = 0
Output: [[0, 0, 0, 0]]

Intuition: Fix Two, Two-Pointer the Rest

You already know the pattern. Three Sum fixed one element and ran a Two Sum two-pointer on the rest. Four Sum takes this one step further: fix two elements with a nested outer loop and run a Two Sum two-pointer on the remaining subarray.

Fix arr[i] and arr[j]. Now find all pairs in arr[j+1..n-1] summing to target − arr[i] − arr[j].

That inner two-pointer is exactly the same Two Sum we’ve been using — sorted array, converging pointers, duplicate skipping. The only addition is a second outer loop and a second level of duplicate skipping.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr"]
  OuterI["for i in 0 → n-4<br/>(fix arr[i])"]
  SkipI{"i > 0 and<br/>arr[i] == arr[i-1]?"}
  OuterJ["for j in i+1 → n-3<br/>(fix arr[j])"]
  SkipJ{"j > i+1 and<br/>arr[j] == arr[j-1]?"}
  SetTP["left = j+1,  right = n-1<br/>need = target − arr[i] − arr[j]"]
  InLoop{"left < right?"}
  Calc["total = arr[left] + arr[right]"]
  Found{"total == need?"}
  Record["append [arr[i], arr[j], arr[left], arr[right]]<br/>skip left & right duplicates<br/>left++,  right--"]
  Less["left++"]
  Greater["right--"]
  Done(["return result"])

  Sort --> OuterI --> SkipI
  SkipI -->|"yes, skip"| OuterI
  SkipI -->|"no"| OuterJ --> SkipJ
  SkipJ -->|"yes, skip"| OuterJ
  SkipJ -->|"no"| SetTP --> InLoop
  InLoop -->|"yes"| Calc --> Found
  Found -->|"yes"| Record --> InLoop
  Found -->|"no, <"| Less --> InLoop
  Found -->|"no, >"| Greater --> InLoop
  InLoop -->|"no"| OuterJ
  OuterJ -->|"done"| OuterI
  OuterI -->|"done"| Done

Four Sum — two nested fixed-element loops, each with duplicate skipping, plus an inner two-pointer Two Sum pass.

Applying the Diagnostic Questions

Four Sum is the clearest demonstration of the two-pointer subproblem pattern because the decomposition happens at two levels before the two-pointer even starts.

Q1 — Why “fix two elements and reduce to Two Sum”?

Mental model: Think of the search space as four dimensions: a + b + c + d = target. Lock two dimensions — a = arr[i], b = arr[j] — and you’re left with two unknowns: c + d = target − arr[i] − arr[j]. Two unknowns on a sorted subarray is Two Sum — the problem you can already solve in O(n). Every additional element you fix collapses one more dimension; you always want to collapse down to exactly Two Sum, because that’s the base case the two-pointer solves optimally.

Concrete numbers: arr = [-2, -1, 0, 0, 1, 2] (sorted), target = 0. Fix arr[0] = -2 and arr[1] = -1. Remaining need: 0 − (−2) − (−1) = 3. Subproblem: find pairs in [0, 0, 1, 2] summing to 3. Two-pointer:

• left=0 (0), right=3 (2): sum 2 < 3 → left++
• left=1 (0), right=3 (2): sum 2 < 3 → left++
• left=2 (1), right=3 (2): sum 3 == 3 ✓ → record [-2, -1, 1, 2]

One fixed pair, one linear inner pass, one quadruplet found.

What breaks if you only fix one element (like Three Sum)? With one fixed element, the inner subproblem is Three Sum — O(n²) — and the outer loop is O(n), giving O(n³). With two fixed elements, the inner subproblem collapses to Two Sum — O(n) — and the two outer loops are O(n²), also giving O(n³). Same final complexity, but the two-level decomposition is cleaner: the innermost operation is always the same O(n) Two Sum core, regardless of how many outer loops wrap it.

The pattern generalisation: Three Sum fixed 1 element to reach Two Sum. Four Sum fixes 2 elements to reach Two Sum. k-Sum fixes k−2 elements to reach Two Sum. The number of fixed elements equals the number of outer loops; the innermost operation is always Two Sum.

Q2 — Why “the inner Two Sum subproblem is solved with two pointers”?

Mental model: After fixing arr[i] and arr[j], you have a sorted subarray arr[j+1..n-1] and a specific need. arr[left] is the minimum of that window; arr[right] is the maximum. Moving left right increases the pair sum; moving right left decreases it. This decisive direction — identical to the reduction section’s Two Sum — is what makes the inner pass O(n) instead of O(n²).

Concrete numbers: subarray [0, 0, 1, 2], need 3:

• left=0 (0), right=3 (2): sum 2 < 3 → moving left is the only way to increase the sum → left++
• left=1 (0), right=3 (2): sum 2 < 3 → same reasoning → left++
• left=2 (1), right=3 (2): sum 3 == 3 → match, record, move both inward
• left=3, right=2: left > right → done

Each decision eliminates one element permanently, so the inner loop runs at most n − j − 1 steps — O(n) total per (i, j) pair.

What if you skipped sorting? Without sorting, arr[left] and arr[right] have no guaranteed min/max relationship. You’d need to try every pair in the subarray — O(n²) inner work instead of O(n) — making the total O(n⁴) instead of O(n³).

Pattern nesting in Four Sum: the outer structure is a two-pointer subproblem pattern at two levels (fix arr[i], then fix arr[j]), and the innermost operation is a two-pointer reduction (sort + Two Sum). The nesting depth of subproblem decompositions determines the exponent in the complexity: Two Sum → O(n), Three Sum → O(n²), Four Sum → O(n³).

Duplicate Skipping — Three Levels

This is the part that trips people up. Duplicates must be skipped at every level independently:

The j > i+1 guard for the inner skip is important — without it, j = i+1 would compare against arr[i] (a different fixed element), incorrectly skipping valid quadruplets.

Solution

from typing import List

class Solution:
    def four_sum(self, arr: List[int], target: int) -> List[List[int]]:
        # Sort the array to enable the two-pointer subproblem approach
        arr.sort()
        n      = len(arr)
        result = []

        for i in range(n - 3):
            # Skip duplicate values for the first fixed element
            if i > 0 and arr[i] == arr[i - 1]:
                continue

            for j in range(i + 1, n - 2):
                # Skip duplicate values for the second fixed element
                # Guard j > i+1 prevents comparing against arr[i] (a different fixed element)
                if j > i + 1 and arr[j] == arr[j - 1]:
                    continue

                # Set up the two-pointer subproblem: find pairs summing to the remaining need
                left, right = j + 1, n - 1
                need = target - arr[i] - arr[j]

                # Run the two-pointer pass on the remaining subarray
                while left < right:
                    total = arr[left] + arr[right]

                    if total == need:
                        result.append([arr[i], arr[j], arr[left], arr[right]])

                        # Skip consecutive left duplicates to avoid duplicate quadruplets
                        while left < right and arr[left] == arr[left + 1]:
                            left += 1
                        # Skip consecutive right duplicates to avoid duplicate quadruplets
                        while left < right and arr[right] == arr[right - 1]:
                            right -= 1

                        # Move both pointers inward after recording the match
                        left  += 1
                        right -= 1

                    elif total < need:
                        # Sum too small — move left pointer to a larger value
                        left += 1
                    else:
                        # Sum too large — move right pointer to a smaller value
                        right -= 1

        return result


# --- Test ---
sol = Solution()
print(sol.four_sum([1, 0, -1, 0, -2, 2], 0))    # [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
print(sol.four_sum([2, 2, 2, 2, 2], 8))          # [[2,2,2,2]]
print(sol.four_sum([1, 2, 3, 4], 100))            # []
print(sol.four_sum([0, 0, 0, 0], 0))             # [[0,0,0,0]]

Dry Run — Example 1

arr = [1, 0, -1, 0, -2, 2] → sorted: [-2, -1, 0, 0, 1, 2], target = 0

i=0, arr[i]=-2:

  j=1, arr[j]=-1, need=0−(−2)−(−1)=3, left=2, right=5:

  j=2, arr[j]=0, need=0−(−2)−0=2, left=3, right=5:

  j=3, arr[j]=0: duplicate of arr[2] (and j > i+1) → skip

  j=4, arr[j]=1, need=0−(−2)−1=1, left=5, right=5: left ≥ right → stop immediately

i=1, arr[i]=-1:

  j=2, arr[j]=0, need=0−(−1)−0=1, left=3, right=5:

  j=3, arr[j]=0: duplicate of arr[2] → skip

  j=4, arr[j]=1, need=0−(−1)−1=0, left=5, right=5: left ≥ right → stop

i=2, arr[i]=0:

  j=3, arr[j]=0, need=0−0−0=0, left=4, right=5:

i=3: n-3=3, loop ends.

Result: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]] ✓

Complexity Analysis

This is the natural cost of searching for 4 elements — each additional fixed element multiplies by O(n). Two Sum is O(n), Three Sum is O(n²), Four Sum is O(n³). You cannot do better than O(n³) for the general k-sum problem with k ≥ 3.

Edge Cases

The k-Sum Generalisation

The pattern is recursive:

• Two Sum: sort + single two-pointer pass → O(n)
• Three Sum: fix 1 element + Two Sum → O(n²)
• Four Sum: fix 2 elements + Two Sum → O(n³)
• k-Sum: fix k−2 elements (k−2 nested loops) + Two Sum → O(nᵏ⁻¹)

Every level adds one outer loop with duplicate skipping. The innermost operation is always the same two-pointer Two Sum.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  TS["Two Sum<br/>O(n)"]
  TH["Three Sum<br/>fix 1 + Two Sum<br/>O(n²)"]
  FO["Four Sum<br/>fix 2 + Two Sum<br/>O(n³)"]
  KS["k-Sum<br/>fix k−2 + Two Sum<br/>O(nᵏ⁻¹)"]

  TS -->|"wrap in one loop"| TH
  TH -->|"wrap in one loop"| FO
  FO -->|"wrap in k−4 loops"| KS

The k-Sum family — each level wraps the previous in one more outer loop with duplicate skipping. Two Sum is always the innermost operation.

Comparison: Three Sum vs Four Sum

The only structural additions are: one more outer loop, one more duplicate-skip block with a careful guard condition, and the need-variable computed from two fixed elements instead of one.

Key Takeaway

Four Sum is the natural extension of Three Sum — add one more fixed-element loop, add one more level of duplicate skipping. The inner two-pointer stays identical. Understanding this telescoping structure reveals the entire k-Sum family: every problem reduces to the same Two Sum core, wrapped in successively more outer loops. Once you have the pattern, adding another level of nesting is mechanical.