Coding Interview Patterns4Sum
MediumTwo Pointers

4Sum

Explanation & Solution

Practice Problem

Description

Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • a, b, c, and d are distinct indices
  • nums[a] + nums[b] + nums[c] + nums[d] == target

The solution set must not contain duplicate quadruplets. You may return the answer in any order.

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

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Explanation: The three distinct quadruplets that sum to 0 are [-2,-1,1,2], [-2,0,0,2], and [-1,0,0,1].

Constraints

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

Approach

Two Pointers pattern

1. Sort the Array

  • Sort nums in ascending order
  • Sorting enables the two-pointer technique and simplifies duplicate skipping

2. Fix the First Element

  • Iterate index i from 0 to nums.length - 4
  • nums[i] is the first element of the quadruplet
  • If nums[i] === nums[i - 1], skip it to avoid duplicate quadruplets

3. Fix the Second Element

  • Iterate index j from i + 1 to nums.length - 3
  • nums[j] is the second element of the quadruplet
  • If nums[j] === nums[j - 1] (and j > i + 1), skip it to avoid duplicates

4. Two-Pointer Search for the Remaining Pair

  • Set left = j + 1 and right = nums.length - 1
  • Compute sum = nums[i] + nums[j] + nums[left] + nums[right]
  • If sum === target: found a valid quadruplet, add it to the result
  • If sum < target: move left right to increase the sum
  • If sum > target: move right left to decrease the sum

5. Skip Duplicates After a Match

  • After finding a valid quadruplet:
  • Advance left past all duplicate values
  • Retreat right past all duplicate values
  • Then move both pointers one more step inward
  • This prevents duplicate quadruplets from being added

6. Return the Result

  • After all iterations complete, return the result array
  • Every quadruplet is unique and sums to the target

Key Insight

  • 4Sum reduces to 3Sum by fixing one element, and 3Sum reduces to 2Sum by fixing another — a classic layered reduction pattern
  • Sorting + two nested loops + two pointers yields an O(n³) solution, far better than the O(n⁴) brute force
  • Duplicate skipping at every level (both outer loops and the inner pointers) is critical for correctness

Visualization

Input:
[1, 0, -1, 0, -2, 2], target = 0
1001-1203-2425
—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone
12 steps

Solution Code

Previous
Trapping Rain Water
Next
Boats to Save People