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.

class Solution:
    def fourSum(self, nums, target):
        rtn = []
        n = len(nums)

        if n < 4:
            return rtn

        nums.sort()

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

                    elif total < target:
                        left += 1
                    else:
                        right -= 1

        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

def four_sum_after_setup(nums, target):
    rtn = []
    n = len(nums)
    if n < 4:
        return rtn
    # ... sort and nested loops follow

2. Sort the Array

nums.sort()

3. Outer Loop (First Number)

for i in range(n - 3):
    if i > 0 and nums[i - 1] == nums[i]:
        continue  # Skip duplicates

4. Inner Loop (Second Number)

for j in range(i + 1, n - 2):
    if j > i + 1 and nums[j - 1] == nums[j]:
        continue  # Skip duplicates

5. Two Pointers (Third and Fourth Numbers)

left, right = j + 1, n - 1
while left < right:
    total = nums[i] + nums[j] + nums[left] + nums[right]
    if total == target:
        rtn.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
    elif total < target:
        left += 1
    else:
        right -= 1

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

# Inside outer loop: skip if remaining numbers can't reach target
for i in range(n - 3):
    if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
        break
    if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
        continue

Similar Optimization for Inner Loop

# Inside inner loop (after fixing i, j)
for j in range(i + 1, n - 2):
    if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
        break
    if 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