4Sum

medium array two pointers sorting

Problem

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

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

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

nums (comma-separated)

target

def four_sum(nums, target):
    nums.sort()
    n, res = 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
            l, r = j + 1, n - 1
            while l < r:
                s = nums[i] + nums[j] + nums[l] + nums[r]
                if s == target:
                    res.append([nums[i], nums[j], nums[l], nums[r]])
                    l += 1; r -= 1
                    while l < r and nums[l] == nums[l-1]: l += 1
                    while l < r and nums[r] == nums[r+1]: r -= 1
                elif s < target: l += 1
                else: r -= 1
    return res

function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  const n = nums.length, res = [];
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let l = j + 1, r = n - 1;
      while (l < r) {
        const s = nums[i] + nums[j] + nums[l] + nums[r];
        if (s === target) {
          res.push([nums[i], nums[j], nums[l], nums[r]]);
          l++; r--;
          while (l < r && nums[l] === nums[l - 1]) l++;
          while (l < r && nums[r] === nums[r + 1]) r--;
        } else if (s < target) l++;
        else r--;
      }
    }
  }
  return res;
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int l = j + 1, r = n - 1;
                while (l < r) {
                    long s = (long) nums[i] + nums[j] + nums[l] + nums[r];
                    if (s == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        l++; r--;
                        while (l < r && nums[l] == nums[l - 1]) l++;
                        while (l < r && nums[r] == nums[r + 1]) r--;
                    } else if (s < target) l++;
                    else r--;
                }
            }
        }
        return res;
    }
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int l = j + 1, r = n - 1;
            while (l < r) {
                long s = (long) nums[i] + nums[j] + nums[l] + nums[r];
                if (s == target) {
                    res.push_back({ nums[i], nums[j], nums[l], nums[r] });
                    l++; r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (s < target) l++;
                else r--;
            }
        }
    }
    return res;
}

Explanation

This extends the 3Sum idea to four numbers that add to a target. After sorting, we fix two outer indices i and j with nested loops, then find the remaining pair using a two-pointer sweep.

With i and j fixed, a left pointer l and right pointer r scan the rest. The sorted order guides them: if s = nums[i]+nums[j]+nums[l]+nums[r] is too small move l right, if too big move r left, and if it equals the target record the quadruplet.

To keep results unique we skip a repeated i (nums[i] == nums[i-1]), a repeated j, and after each match we skip equal nums[l] and nums[r] values.

Example: sorted [-2, -1, 0, 0, 1, 2], target 0. Fixing -2 and -1, the pair 1 and 2 completes [-2, -1, 1, 2].

Two fixed indices plus a linear sweep gives an n-cubed solution, and the duplicate-skipping is what guarantees no quadruplet is listed twice.

Time: O(n³) Space: O(1) auxiliary