Course4all
Join us on telegram
Home/dsa/Two Pointers/4Sum

4Sum

Master this topic with zero to advance depth.

4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that their sum is equal to target (0 <=q a, b, c, d < n and are distinct).

Visual Representation

Sorted: [-2, -1, 0, 0, 1, 2], Target: 0 Step 1: Fix i = -2, j = -1 L = 0, R = 2 Sum = -2 + (-1) + 1 + 2 = 0 -> FOUND! [-2, -1, 1, 2] Step 2: Fix i = -2, j = 0 L = 0, R = 2 Sum = -2 + 0 + 0 + 2 = 0 -> FOUND! [-2, 0, 0, 2]
Medium

Examples

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

There are three unique quadruplets that sum to 0.

Approach 1

Level I: Brute Force (Check All Quadruplets)

Intuition

Try every possible combination of four numbers to see if they sum up to the target. To avoid duplicates, we sort each quadruplet and store it in a Set.

⏱ O(N^4)💾 O(K) where K is the number of unique quadruplets

Detailed Dry Run

Input: [1, 0, -1, 0, -2, 2], Target: 0 Combination (1, 0, -1, 0) -> Sum 0. Found! Combination (1, 0, -2, 2) -> Sum 1. Skip. ...

java
public List<List<Integer>> fourSum(int[] nums, int target) {
    Set<List<Integer>> res = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    if ((long)nums[i] + nums[j] + nums[k] + nums[l] == target) {
                        List<Integer> q = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                        Collections.sort(q);
                        res.add(q);
                    }
                }
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^4) will TLE for N > 200.

Approach 2

Level II: Sorting + HashSet

Intuition

By sorting and using a HashSet for the fourth element, we can reduce the complexity to O(N^3). It's essentially 3Sum but with one more outer loop.

Fix three pointers i, j, k, and check if target - (nums[i] + nums[j] + nums[k]) exists in a HashSet of the remaining elements.

⏱ O(N^3)💾 O(N)

Detailed Dry Run

Input: [1, 0, -1, 0, -2, 2], Target: 0

  1. Fix 1, 0, -1. Need 0. Found 0 in the array. Quads: [1, 0, -1, 0].
  2. Fix 1, 0, -2. Need 1. Found 1. Quads: [1, 0, -2, 1]... No, 1 was already used. Use indices to avoid reuse.
java
public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    Set<List<Integer>> res = new HashSet<>();
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                long rem = (long)target - nums[i] - nums[j] - nums[k];
                int low = k + 1, high = n - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (nums[mid] == rem) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[k], (int)rem));
                        break;
                    }
                    if (nums[mid] < rem) low = mid + 1;
                    else high = mid - 1;
                }
            }
        }
    }
    return new ArrayList<>(res);
}

⚠️ Common Pitfalls & Tips

O(N^3) is still slow for very large constraints but works for N=200-500.

Approach 3

Level III: Optimal (Sort + Two Pointers)

Intuition

This is a direct extension of 3Sum. We sort the array and use two nested loops to fix the first two numbers (i and j). Then we use the Two Pointer technique to find the remaining two numbers (L and R).

⏱ O(N^3)💾 O(1) (excluding sorting space)

Detailed Dry Run

Sorted: [-2, -1, 0, 0, 1, 2], Target: 0

ijLRSumAction
-2-101-3Sum < 0, L++
-2-1120FOUND! L++, R--
-20020FOUND! L++, R--
java
import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        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 sum = (long)nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++; r--;
                    } else if (sum < target) l++;
                    else r--;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
    }
}

⚠️ Common Pitfalls & Tips

Be mindful of integer overflow in Java/C++ when adding four large integers. Use long or long long for the sum.

← Previous Question3Sum
Next Question →Sort Colors