3.6 4Sum

3.6.1 Problem Metadata

3.6.2 Description

Given an integer array nums and an integer target, return all unique quadruplets [a, b, c, d] such that a + b + c + d = target. No duplicate quadruplets may appear in the answer.

Note: This problem is part of the N Sum Family pattern. See the comparison table in the chapter introduction for a comprehensive comparison of all Two Sum, Three Sum, and Four Sum variants.

3.6.3 Examples

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

3.6.4 Constraints

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

3.6.5 Solution - Nested Two Pointers

3.6.5.1 Walkthrough

Sort the array, then fix two indices i and j. For each pair, run a two-pointer search on the remaining suffix to find the other two numbers. Skip duplicate values for every index to avoid repeating the same quadruplet.

3.6.5.2 Analysis

  • Time Complexity: O(n^3)
  • Space Complexity: O(1) auxiliary (excluding output)

3.6.5.3 Implementation Steps

  1. Sort nums.
  2. For each i from 0 to n - 4 (skipping duplicates):
    1. For each j from i + 1 to n - 3 (skipping duplicates):
      • Set left = j + 1, right = n - 1.
      • While left < right, evaluate sum = nums[i] + nums[j] + nums[left] + nums[right].
      • If sum == target, record the quadruplet and move both pointers past duplicates.
      • Otherwise shift the pointer whose movement drives the sum toward target.
  3. Return the lc-list of quadruplets.

3.6.5.4 Code - Java

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < nums.length - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            int left = j + 1;
            int right = nums.length - 1;

            while (left < right) {
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];

                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));

                    int leftVal = nums[left];
                    int rightVal = nums[right];
                    while (left < right && nums[left] == leftVal) {
                        left++;
                    }
                    while (left < right && nums[right] == rightVal) {
                        right--;
                    }
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }

    return result;
}