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

Thinking Process

  1. Sorting First: Sorting allows us to use two pointers and skip duplicates efficiently
  • Two indices move toward each other or in the same direction.
  • Works on sorted arrays or when in-place modification is required.
  • Loop invariant: all indices outside [left, right] are already resolved.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Solution

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.

// import java.util.Arrays;
// import java.util.Collections;
class Solution {
    public int[][] fourSum(int[] nums, int target) {
        List<int[]> rtn = new ArrayList<>();
        int n = nums.length;
        if(n < 4) return rtn;

        Arrays.sort(nums);

        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 sum = (long)nums[i] + nums[j] + nums[left] + nums[right];

                    if (sum == target) {
                        rtn.add({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;
    }
}

Solution Explanation

Approach: Opposite ends (this problem)

Key idea: 1. Sorting First: Sorting allows us to use two pointers and skip duplicates efficiently

How the code works:

  1. Sorting First: Sorting allows us to use two pointers and skip duplicates efficiently
    • Two indices move toward each other or in the same direction.
    • Works on sorted arrays or when in-place modification is required.
    • Loop invariant: all indices outside [left, right] are already resolved.

Walkthrough — input nums = [1,0,-1,0,-2,2], target = 0, expected output [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

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

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

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

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

  5. Integer Overflow: Not using long long for sum calculation
  6. Duplicate Handling: Not properly skipping duplicates after finding a match
  7. Index Bounds: Not checking n < 4 before processing
  8. 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;

References

Key Takeaways

  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