medium

4Sum

Find every unique quadruplet of numbers in an array that adds up to a target value.

1. Define the problem

4Sum

Given an array nums of n integers and an integer target, return an array of all the unique quadruplets [numsa, numsb, numsc, numsd] such that a, b, c, and d are distinct indices, and numsa + numsb + numsc + numsd == target. The solution set must not contain duplicate quadruplets . This generalizes 3Sum: fix two elements with nested outer loops instead of one, then run converging two pointers on the remainder — skipping repeated values at every level of both loops and the inner scan.

Constraints

  • 1 ≤ nums.length ≤ 200
  • -109 ≤ numsi ≤ 109
  • -109 ≤ target ≤ 109

Example

Inputnums = [1, 0, -1, 0, -2, 2], target = 0
Output[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Explanation Sorting gives [-2, -1, 0, 0, 1, 2]. Fixing each pair of outer elements and converging two pointers on the rest finds exactly three distinct quadruplets that sum to 0.

2. Know the words first

In plain terms

Quadruplet
A group of exactly four values picked from the array, like picking four friends out of a group.
3. Visualize the solution

Two nested anchors, then converge on the rest

Two nested anchors, then converge on the rest
Statusinit

Fix outer anchors nums[0]=-2, nums[1]=-1 (i=0, j=1). left=2, right=5: sum = -2 + -1 + 0 + 2 = -1 < 0, move left inward.

What happens in this step

i = 0 (value -2), j = 1 (value -1)
left = 2 (value 0), right = 5 (value 2)
sum = -2 + -1 + 0 + 2 = -1

-1 < target (0), so left moves inward from index 2 to index 3.
Step 1 of 4

Steps to visualize

  1. Sort the array so duplicate values sit together and sums move monotonically.
  2. Fix the outer index i, skipping it if it repeats the previous i.
  3. Fix the inner index j after i, skipping it if it repeats the previous j at this level.
  4. Set left just after j and right at the end, then converge them the same way as 3Sum.
  5. If the four-way sum matches target, record the quadruplet and skip past duplicates on both sides before moving both pointers inward.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two nested anchors, then converge on the rest
Statusinit

Fix outer anchors nums[0]=-2, nums[1]=-1 (i=0, j=1). left=2, right=5: sum = -2 + -1 + 0 + 2 = -1 < 0, move left inward.

What happens in this step

i = 0 (value -2), j = 1 (value -1)
left = 2 (value 0), right = 5 (value 2)
sum = -2 + -1 + 0 + 2 = -1

-1 < target (0), so left moves inward from index 2 to index 3.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function fourSum(nums, target) {
  const sorted = [...nums].sort((a, b) => a - b);
  const n = sorted.length;
  const result = [];

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && sorted[i] === sorted[i - 1]) {
      continue;
    }

    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && sorted[j] === sorted[j - 1]) {
        continue;
      }

      let left = j + 1;
      let right = n - 1;

      while (left < right) {
        const sum = sorted[i] + sorted[j] + sorted[left] + sorted[right];

        if (sum === target) {
          result.push([sorted[i], sorted[j], sorted[left], sorted[right]]);
          while (left < right && sorted[left] === sorted[left + 1]) {
            left++;
          }
          while (left < right && sorted[right] === sorted[right - 1]) {
            right--;
          }
          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }

  return result;
}
Time
O(n^3)
Space
O(n) (for the sort; excluding the output array)
6. Test cases

Test cases

InputExpectedCovers
nums = [1, 0, -1, 0, -2, 2], target = 0[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]example from the docstring
nums = [1, 2, 3, 4], target = 10[[1, 2, 3, 4]]smallest valid input: exactly four elements
nums = [1, 2, 3], target = 6[]array shorter than four elements returns empty
nums = [2, 2, 2, 2, 2], target = 0[]no combination of four values reaches the target
nums = [2, 2, 2, 2, 2, 2], target = 8[[2, 2, 2, 2]]many duplicate values collapse to a single deduplicated quadruplet

Keep reading