[Medium] 18. 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:

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

You may return the answer in any order.

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]]

Example 2:

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

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Quadruplet definition: What is a valid quadruplet? (Assumption: Four distinct indices (i, j, k, l) where nums[i] + nums[j] + nums[k] + nums[l] == target)

  2. Uniqueness: Should quadruplets be unique? (Assumption: Yes - no duplicate quadruplets in result, but can use same value at different indices)

  3. Return format: What should we return? (Assumption: List of all unique quadruplets - list of lists)

  4. Order requirement: Does order of quadruplets matter? (Assumption: No - can return in any order, but typically sorted)

  5. Duplicate values: How should we handle duplicate values? (Assumption: Can use same value multiple times if at different indices, but avoid duplicate quadruplets)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Use four nested loops to try all combinations of four indices (i, j, k, l). Check if nums[i] + nums[j] + nums[k] + nums[l] == target. Collect all valid quadruplets, then remove duplicates. This approach has O(n⁴) time complexity, which is too slow for arrays up to 200 elements. Duplicate removal adds additional overhead.

Step 2: Semi-Optimized Approach (7 minutes)

Use three nested loops and a hash set for the fourth value. For each combination of three indices (i, j, k), check if target - (nums[i] + nums[j] + nums[k]) exists in a hash set of remaining values. This reduces to O(n³) time complexity. However, handling duplicates and ensuring we use distinct indices requires careful bookkeeping. Sorting the array first helps with duplicate handling.

Step 3: Optimized Solution (8 minutes)

Sort the array first, then use two nested loops for the first two numbers, and two pointers for the remaining two numbers. For each pair (i, j), use left and right pointers to find pairs (k, l) such that nums[i] + nums[j] + nums[k] + nums[l] == target. Skip duplicates by advancing pointers when values repeat. This achieves O(n³) time complexity with O(1) extra space (excluding output). The key insight is that sorting enables two-pointer technique and makes duplicate skipping straightforward, providing an optimal balance between time complexity and code clarity.

Solution: Two Pointers with Nested Loops

Time Complexity: O(n³)
Space Complexity: O(1) excluding the output array

This solution extends the 3Sum approach with an additional nested loop. We use two nested loops to fix the first two numbers, then use two pointers to find the remaining two numbers that sum to the target.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> rtn;
        const int n = nums.size();
        if(n < 4) return rtn;

        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < n - 3; i++) {
            if(i > 0 && nums[i - 1] == nums[i]) 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) {
                        rtn.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--;
                    } else if(sum < target) left++;
                    else right--;
                }
            }
        }
        return rtn;
    }
};

How the Algorithm Works

Step-by-Step Example: nums = [1,0,-1,0,-2,2], target = 0

After sorting: [-2, -1, 0, 0, 1, 2]

  1. i = 0, nums[i] = -2: Fix first number
    • j = 1, nums[j] = -1: Fix second number
      • left = 2, right = 5: -2 + (-1) + 0 + 2 = -1 < 0 → left++
      • left = 3, right = 5: -2 + (-1) + 0 + 2 = -1 < 0 → left++
      • left = 4, right = 5: -2 + (-1) + 1 + 2 = 0 → Found! [-2, -1, 1, 2]
    • j = 2, nums[j] = 0: Fix second number
      • left = 3, right = 5: -2 + 0 + 0 + 2 = 0 → Found! [-2, 0, 0, 2]
  2. i = 1, nums[i] = -1: Fix first number
    • j = 2, nums[j] = 0: Fix second number
      • left = 3, right = 5: -1 + 0 + 0 + 1 = 0 → Found! [-1, 0, 0, 1]

Final Answer: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Key Insights

  1. Sorting First: Sorting allows us to use two pointers and skip duplicates efficiently
  2. Nested Loops: Two outer loops fix the first two numbers (i, j)
  3. Two Pointers: Inner loop uses two pointers to find the remaining two numbers
  4. Skip Duplicates: After finding a valid quadruplet, skip all duplicate values
  5. Long Long for Sum: Use long long to prevent integer overflow

Algorithm Breakdown

1. Base Case Check

if(n < 4) return rtn;

2. Sort the Array

sort(nums.begin(), nums.end());

3. Outer Loop (First Number)

for(int i = 0; i < n - 3; i++) {
    if(i > 0 && nums[i - 1] == nums[i]) continue;  // Skip duplicates

4. Inner Loop (Second Number)

for(int j = i + 1; j < n - 2; j++) {
    if(j > i + 1 && nums[j] == nums[j - 1]) continue;  // Skip duplicates

5. Two Pointers (Third and Fourth Numbers)

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) {
        // Found a valid quadruplet
        rtn.push_back({nums[i], nums[j], nums[left], nums[right]});
        // Skip duplicates
        while(left < right && nums[left] == nums[left + 1]) left++;
        while(left < right && nums[right] == nums[right - 1]) right--;
        left++;
        right--;
    } else if(sum < target) left++;
    else right--;
}

Complexity Analysis

Aspect Complexity
Time O(n³) - Two nested loops O(n²) × two pointers O(n)
Space O(1) - Excluding the output array, only using a few variables

Edge Cases

  1. Array length < 4: Return empty array
  2. All same numbers: [2,2,2,2,2], target = 8 → [[2,2,2,2]]
  3. No solution: Return empty array
  4. Large numbers: Use long long to prevent overflow

Why This Solution is Optimal

  1. Efficient: O(n³) is optimal for this problem (cannot do better than checking combinations)
  2. No Duplicates: Properly skips duplicates using sorted array property
  3. Early Termination: Could add early termination if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target
  4. Space Efficient: Only uses O(1) extra space

Common Mistakes

  1. Integer Overflow: Not using long long for sum calculation
  2. Duplicate Handling: Not properly skipping duplicates after finding a match
  3. Index Bounds: Not checking n < 4 before processing
  4. Wrong Skip Condition: Using j > 0 instead of j > i + 1 for the second number

Optimization Tips

Early Termination

// Skip if remaining numbers can't form target
if((long long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
if((long long)nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;

Similar Optimization for Inner Loop

if((long long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
if((long long)nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) continue;