Skip to main content
CodePeetCodePeet
CodePeet 250

4Sum

MEDIUMProblemSolveExternal Links

Description

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

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

You may return the answer in any order. Each quadruplet must be unique — no two quadruplets should contain the same set of four values regardless of ordering.

Examples

Example 1

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

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

Explanation: There are three unique quadruplets that sum to 0:

  • (-2) + (-1) + 1 + 2 = 0
  • (-2) + 0 + 0 + 2 = 0
  • (-1) + 0 + 0 + 1 = 0

No other combination of four distinct indices produces a sum of 0.

Example 2

Input: nums = [2, 2, 2, 2, 2], target = 8

Output: [[2, 2, 2, 2]]

Explanation: All elements are 2. The only quadruplet is [2, 2, 2, 2] with sum 2 + 2 + 2 + 2 = 8. Even though there are multiple ways to pick four indices, they all yield the same values, so only one unique quadruplet is returned.

Example 3

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

Output: []

Explanation: No four elements in the array sum to 100, so we return an empty list.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to find four numbers that sum to a target is to simply try every possible combination of four numbers from the array.

Imagine you have a bag of numbered balls. You pick up the first ball, then try every possible second ball, then every possible third ball, and finally every possible fourth ball. For each group of four, you check if their numbers add up to the target. If they do, and you haven't already recorded that exact group, you keep it.

This approach requires four nested loops — one for each element in the quadruplet. Because we need unique quadruplets, we sort each found quadruplet and use a set to filter duplicates.

Step-by-Step Explanation

Let's trace through with nums = [1, 0, -1, 0], target = 0:

Step 1: Fix i=0 (value 1). We need three more numbers summing to 0 - 1 = -1.

Step 2: Fix j=1 (value 0). We need two more numbers summing to -1 - 0 = -1.

Step 3: Fix k=2 (value -1). We need one more number equal to -1 - (-1) = 0.

Step 4: Check l=3 (value 0). Sum = 1 + 0 + (-1) + 0 = 0. This equals our target!

Step 5: Sort the quadruplet [1, 0, -1, 0] → [-1, 0, 0, 1]. Add to result set.

Step 6: Continue checking all remaining combinations of (i, j, k, l). No other quadruplet sums to 0 with these four elements.

Result: [[-1, 0, 0, 1]]

Brute Force — Checking All Quadruplets — Watch how four nested pointers systematically try every combination of four elements, checking if their sum equals the target.

Algorithm

  1. Initialize a set to track unique quadruplets (to avoid duplicates)
  2. Run four nested loops with indices i, j, k, l where i < j < k < l:
    • Compute sum = nums[i] + nums[j] + nums[k] + nums[l]
    • If sum equals target:
      • Sort the quadruplet [nums[i], nums[j], nums[k], nums[l]]
      • Add to result set if not already present
  3. Convert the set to a list and return

Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        set<vector<int>> resSet;
        
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        long long sum = (long long)nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum == target) {
                            vector<int> quad = {nums[i], nums[j], nums[k], nums[l]};
                            sort(quad.begin(), quad.end());
                            resSet.insert(quad);
                        }
                    }
                }
            }
        }
        
        return vector<vector<int>>(resSet.begin(), resSet.end());
    }
};
class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        n = len(nums)
        result_set = set()
        
        for i in range(n - 3):
            for j in range(i + 1, n - 2):
                for k in range(j + 1, n - 1):
                    for l in range(k + 1, n):
                        if nums[i] + nums[j] + nums[k] + nums[l] == target:
                            quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                            result_set.add(quad)
        
        return [list(q) for q in result_set]
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Set<List<Integer>> resSet = new HashSet<>();
        
        for (int i = 0; i < n - 3; i++) {
            for (int j = i + 1; j < n - 2; j++) {
                for (int k = j + 1; k < n - 1; k++) {
                    for (int l = k + 1; l < n; l++) {
                        long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum == target) {
                            List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
                            Collections.sort(quad);
                            resSet.add(quad);
                        }
                    }
                }
            }
        }
        
        return new ArrayList<>(resSet);
    }
}

Complexity Analysis

Time Complexity: O(n⁴ · log n)

The four nested loops generate O(n⁴) combinations. For each valid quadruplet, sorting it takes O(4 log 4) = O(1), and inserting into the set takes O(log(set size)). In the worst case, the set operations add a logarithmic factor, giving us O(n⁴ · log n) overall.

Space Complexity: O(n⁴)

In the worst case (all elements the same and sum equals target), we store up to C(n, 4) quadruplets in the set, which is O(n⁴). In practice, the number of valid quadruplets is typically much smaller.

Why This Approach Is Not Efficient

The brute force uses four nested loops, resulting in O(n⁴) time complexity. With n up to 200, this means 200⁴ = 1.6 × 10⁹ operations — far too many for typical time limits of 1-2 seconds.

The fundamental issue is that we are checking every possible combination of four elements without leveraging any mathematical structure. For each pair of two fixed elements, we do a linear scan through all remaining pairs. If we could reduce the innermost search from O(n²) to something faster, we would save significant time.

Key insight: By sorting the array first, we can use the two-pointer technique to find the third and fourth elements in O(n) time instead of O(n²). This reduces the overall complexity from O(n⁴) to O(n³).

Better Approach - Hashing

Intuition

Instead of using a fourth nested loop, we can use a hash set to find the fourth element in O(1) average time. The idea is similar to how we solve Two Sum with a hash map — but extended to four elements.

We fix the first two elements with two nested loops (indices i and j). Then, for the third element (index k), we compute what the fourth element needs to be: need = target - nums[i] - nums[j] - nums[k]. We check if this value has been seen already in a hash set that tracks elements between indices j+1 and k-1.

Think of it like shopping with a fixed budget. You've picked your first two items, and now you're walking through the remaining items. For each item you see, you check if the exact remaining budget is something you've encountered earlier on this walk. If it is, you've found your group.

Step-by-Step Explanation

Let's trace through with nums = [1, 0, -1, 0, -2, 2], target = 0:

Step 1: Fix i=0 (value 1), j=1 (value 0). Two-element sum = 1 + 0 = 1. Remaining target = 0 - 1 = -1.

Step 2: Create an empty hash set for this (i, j) pair. Process k=2: value = -1. Need = -1 - (-1) = 0. Is 0 in hash set? No (set is empty). Add -1 to set. Set = {-1}.

Step 3: Process k=3: value = 0. Need = -1 - 0 = -1. Is -1 in hash set? YES! Found quadruplet: sort [1, 0, -1, 0] → [-1, 0, 0, 1]. Add 0 to set. Set = {-1, 0}.

Step 4: Process k=4: value = -2. Need = -1 - (-2) = 1. Is 1 in hash set? No. Add -2 to set. Set = {-1, 0, -2}.

Step 5: Process k=5: value = 2. Need = -1 - 2 = -3. Is -3 in hash set? No. Done with (i=0, j=1).

Step 6: Fix i=0 (value 1), j=2 (value -1). Two-element sum = 1 + (-1) = 0. Remaining target = 0. Fresh hash set.

Step 7: k=3: value 0, need = 0 - 0 = 0, not in set. Add 0. k=4: value -2, need = 0 - (-2) = 2, not in set. Add -2. k=5: value 2, need = 0 - 2 = -2, YES! Found [-2, -1, 1, 2].

Step 8: Continue for all (i, j) pairs. Eventually find [-2, 0, 0, 2] and [-1, 0, 0, 1] as well.

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

Hashing Approach — Finding the Fourth Element via Lookup — Watch how for each fixed pair (i, j), we use a hash set to find matching fourth elements in O(1) time as we scan through potential third elements.

Algorithm

  1. Initialize a set to store unique sorted quadruplets
  2. For each index i from 0 to n-1:
    • For each index j from i+1 to n-1:
      • Create an empty hash set for this (i, j) pair
      • For each index k from j+1 to n-1:
        • Compute need = target - nums[i] - nums[j] - nums[k]
        • If need exists in the hash set: sort [nums[i], nums[j], nums[k], need] and add to result set
        • Add nums[k] to the hash set
  3. Return the result set as a list

Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        set<vector<int>> resSet;
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                unordered_set<long long> seen;
                for (int k = j + 1; k < n; k++) {
                    long long need = (long long)target - nums[i] - nums[j] - nums[k];
                    if (seen.count(need)) {
                        vector<int> quad = {nums[i], nums[j], nums[k], (int)need};
                        sort(quad.begin(), quad.end());
                        resSet.insert(quad);
                    }
                    seen.insert(nums[k]);
                }
            }
        }
        
        return vector<vector<int>>(resSet.begin(), resSet.end());
    }
};
class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        n = len(nums)
        result_set = set()
        
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                seen = set()
                for k in range(j + 1, n):
                    need = target - nums[i] - nums[j] - nums[k]
                    if need in seen:
                        quad = tuple(sorted([nums[i], nums[j], nums[k], need]))
                        result_set.add(quad)
                    seen.add(nums[k])
        
        return [list(q) for q in result_set]
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Set<List<Integer>> resSet = new HashSet<>();
        
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                Set<Long> seen = new HashSet<>();
                for (int k = j + 1; k < n; k++) {
                    long need = (long) target - nums[i] - nums[j] - nums[k];
                    if (seen.contains(need)) {
                        List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[k], (int) need);
                        Collections.sort(quad);
                        resSet.add(quad);
                    }
                    seen.add((long) nums[k]);
                }
            }
        }
        
        return new ArrayList<>(resSet);
    }
}

Complexity Analysis

Time Complexity: O(n³)

We have two outer loops (i and j) giving O(n²) iterations. For each pair, the inner loop k runs in O(n), and the hash set lookup/insertion is O(1) on average. Total: O(n²) × O(n) = O(n³). Using a set for duplicate checking adds a logarithmic factor per insertion.

Space Complexity: O(n + k)

The hash set for each (i, j) pair stores at most O(n) elements. The result set stores k unique quadruplets. In the worst case, k can be O(n²), so total space is O(n²).

Why This Approach Is Not Efficient

While the hashing approach reduces time from O(n⁴) to O(n³), it has two practical drawbacks:

  1. Extra space: The hash set requires O(n) extra memory for each (i, j) pair, and the outer result set stores all found quadruplets. This adds up.

  2. Duplicate handling overhead: We sort each quadruplet and insert into a set to avoid duplicates. This sorting and set comparison adds constant overhead per found quadruplet, but more importantly, the approach doesn't prevent generating duplicate quadruplets in the first place — it only filters them out after the fact.

A better approach would avoid generating duplicates altogether. By sorting the array first and using smart skip logic with the two-pointer technique, we can achieve O(n³) time with O(1) extra space (excluding the output) and no need for a separate deduplication set.

Optimal Approach - Sorting + Two Pointers

Intuition

This approach builds on a powerful idea: if the array is sorted, we can use the two-pointer technique to find pairs that sum to a specific value in O(n) time.

Here's the strategy:

  1. Sort the array first.
  2. Use two outer loops to fix the first two elements (indices i and j).
  3. For the remaining two elements, use two pointers (left starting at j+1, right starting at end) that converge toward each other.
  4. If the four-element sum is too small, move the left pointer right (to increase the sum). If too large, move the right pointer left (to decrease the sum).

To avoid duplicate quadruplets without extra data structures, we skip over duplicate values in each loop. Since the array is sorted, duplicates are adjacent, making them easy to detect.

Think of it like tuning two radio dials simultaneously. You've fixed two channels (i and j), and now you have a low dial (left) and a high dial (right). If the combined signal is too weak (sum too small), turn the low dial up. If too strong (sum too large), turn the high dial down. When you hit the target frequency, record it and skip past any identical dial settings.

Step-by-Step Explanation

Let's trace through with nums = [1, 0, -1, 0, -2, 2], target = 0.

Step 1: Sort the array: [-2, -1, 0, 0, 1, 2].

Step 2: Fix i=0 (value -2). Fix j=1 (value -1). Two-element sum = -3. Set left=2, right=5.

Step 3: left=2 (value 0), right=5 (value 2). Sum = -2 + (-1) + 0 + 2 = -1. Sum < 0, so move left pointer right.

Step 4: left=3 (value 0), right=5 (value 2). Sum = -2 + (-1) + 0 + 2 = -1. Sum < 0, move left right again.

Step 5: left=4 (value 1), right=5 (value 2). Sum = -2 + (-1) + 1 + 2 = 0. Sum equals target! Record quadruplet [-2, -1, 1, 2]. Move both pointers inward. left=5, right=4 → left > right, done.

Step 6: Fix i=0 (value -2), j=2 (value 0). Two-element sum = -2. Set left=3, right=5.

Step 7: left=3 (value 0), right=5 (value 2). Sum = -2 + 0 + 0 + 2 = 0. Match! Record [-2, 0, 0, 2]. Skip duplicates, move pointers. left=4, right=4 → left >= right, done.

Step 8: Fix i=0, j=3 (value 0). But nums[3] == nums[2] = 0 → skip duplicate j.

Step 9: Fix i=1 (value -1), j=2 (value 0). Sum = -1 + 0 = -1. Set left=3, right=5.

Step 10: left=3 (value 0), right=5 (value 2). Sum = -1 + 0 + 0 + 2 = 1. Sum > 0, move right left.

Step 11: left=3 (value 0), right=4 (value 1). Sum = -1 + 0 + 0 + 1 = 0. Match! Record [-1, 0, 0, 1]. Move pointers. Done.

Step 12: Continue remaining (i, j) pairs. No more valid quadruplets found.

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

Sorting + Two Pointers — Converging to Find Quadruplets — Watch how after sorting, two outer loops fix the first two elements while two pointers converge from opposite ends to find the remaining pair, skipping duplicates along the way.

Algorithm

  1. Sort the array in ascending order
  2. For each index i from 0 to n-4:
    • Skip if nums[i] == nums[i-1] (avoid duplicate first element)
    • For each index j from i+1 to n-3:
      • Skip if j > i+1 and nums[j] == nums[j-1] (avoid duplicate second element)
      • Set left = j+1, right = n-1
      • While left < right:
        • Compute sum = nums[i] + nums[j] + nums[left] + nums[right]
        • If sum < target: move left right (increase sum)
        • If sum > target: move right left (decrease sum)
        • If sum == target:
          • Add [nums[i], nums[j], nums[left], nums[right]] to result
          • Skip duplicates for left (while nums[left] == nums[left+1])
          • Skip duplicates for right (while nums[right] == nums[right-1])
          • Move left right and right left
  3. Return result

Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        if (n < 4) return result;
        
        sort(nums.begin(), nums.end());
        
        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 left = j + 1, right = n - 1;
                
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        
                        left++;
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        nums.sort()
        result = []
        n = 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
                
                left = j + 1
                right = n - 1
                
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if total < target:
                        left += 1
                    elif total > target:
                        right -= 1
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1
                        
                        left += 1
                        right -= 1
        
        return result
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        if (n < 4) return result;
        
        Arrays.sort(nums);
        
        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 left = j + 1, right = n - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        
                        left++;
                        right--;
                    }
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n³)

Sorting takes O(n log n). The two outer loops iterate O(n²) times. For each fixed (i, j) pair, the two-pointer search runs in O(n) time because left and right pointers together traverse at most n elements. Total: O(n log n) + O(n² × n) = O(n³).

While this is the same Big-O as the hashing approach, it is faster in practice because: (1) no hash set overhead, (2) no duplicate sorting per quadruplet, and (3) better cache locality from sequential array access.

Space Complexity: O(1) (excluding output)

The sorting is done in-place. The two pointers and loop variables use constant space. The only additional space is the output list itself, which is required by the problem.