Problem Description

You are given an array nums containing n integers and a target value. Your task is to find all unique quadruplets (groups of four numbers) from the array that sum up to the target value.

A valid quadruplet [nums[a], nums[b], nums[c], nums[d]] must satisfy these conditions:

• All four indices a, b, c, and d are different (you cannot use the same element twice)
• The indices must be within the valid range: 0 <= a, b, c, d < n
• The sum of the four elements equals the target: nums[a] + nums[b] + nums[c] + nums[d] == target
• The quadruplet must be unique (no duplicate quadruplets in the result)

The solution uses a combination of sorting and the two-pointer technique. After sorting the array, it fixes the first two elements through nested loops and uses two pointers to find the remaining two elements. The sorting helps in:

1. Efficiently skipping duplicate values to ensure unique quadruplets
2. Using the two-pointer approach for the last two elements

The algorithm works by:

• Iterating through possible values for the first element (index i)
• For each i, iterating through possible values for the second element (index j where j > i)
• Using two pointers k and l (where k starts right after j and l starts at the end) to find pairs that complete the quadruplet
• Adjusting pointers based on whether the current sum is less than, greater than, or equal to the target
• Skipping duplicate values at each level to avoid duplicate quadruplets in the result

The time complexity is O(n³) due to the three nested loops (two explicit loops and one implicit loop from the two-pointer traversal).

Intuition

The key insight is recognizing this as an extension of the classic Two Sum and Three Sum problems. When we need to find combinations that sum to a target, sorting the array opens up powerful optimization opportunities.

Think about how we'd solve this naively: we'd need four nested loops to check every possible combination of four numbers, giving us O(n⁴) time complexity. But can we do better?

The breakthrough comes from realizing that once we fix two numbers, finding the other two becomes a Two Sum problem on a sorted array. In a sorted array, we can use two pointers moving from opposite ends to efficiently find pairs that sum to a specific value.

Why does this work? When we have a sorted array and two pointers at opposite ends:

• If the current sum is too small, we need a larger number, so we move the left pointer right (to a larger value)
• If the current sum is too large, we need a smaller number, so we move the right pointer left (to a smaller value)
• If we find the target sum, we record it and move both pointers inward

The beauty of sorting first is that it also helps us handle duplicates elegantly. When we encounter the same value multiple times, we can simply skip over the duplicates since we've already processed all combinations with that value. This prevents duplicate quadruplets in our result without needing a separate deduplication step.

So our strategy becomes:

1. Sort the array to enable two-pointer technique and easy duplicate handling
2. Fix the first two elements using nested loops
3. For each pair of fixed elements, use two pointers to find all valid pairs for the remaining two positions
4. Skip duplicates at each level to ensure unique quadruplets

This reduces our time complexity from O(n⁴) to O(n³), which is a significant improvement for large arrays.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

Let's walk through the implementation step by step, following the sorting + double pointers approach.

Step 1: Initial Setup and Sorting

First, we sort the array to enable the two-pointer technique and make duplicate handling easier:

nums.sort()

We also check if the array has fewer than 4 elements, as we need at least 4 numbers to form a quadruplet.

Step 2: Fix the First Element

We iterate through the array to fix the first element nums[i]:

for i in range(n - 3):  # Stop at n-3 since we need 3 more elements
    if i and nums[i] == nums[i - 1]:
        continue  # Skip duplicates for the first element

The condition i and nums[i] == nums[i - 1] ensures we skip duplicate values for the first position (except when i = 0).

Step 3: Fix the Second Element

For each fixed first element, we iterate to fix the second element nums[j]:

for j in range(i + 1, n - 2):  # Start after i, stop at n-2
    if j > i + 1 and nums[j] == nums[j - 1]:
        continue  # Skip duplicates for the second element

Step 4: Two Pointers for the Last Two Elements

With the first two elements fixed, we use two pointers to find valid pairs for positions 3 and 4:

k, l = j + 1, n - 1  # k starts right after j, l starts at the end
while k < l:
    x = nums[i] + nums[j] + nums[k] + nums[l]

Step 5: Adjust Pointers Based on Sum

We calculate the sum x and compare it with the target:

• If x < target: The sum is too small, so we move k forward to get a larger value
• If x > target: The sum is too large, so we move l backward to get a smaller value
• If x == target: We found a valid quadruplet!

When we find a valid quadruplet:

ans.append([nums[i], nums[j], nums[k], nums[l]])
k, l = k + 1, l - 1  # Move both pointers inward

Step 6: Skip Duplicates for the Two Pointers

After finding a valid quadruplet, we skip duplicate values to avoid duplicate results:

while k < l and nums[k] == nums[k - 1]:
    k += 1  # Skip duplicate values for k
while k < l and nums[l] == nums[l + 1]:
    l -= 1  # Skip duplicate values for l

Note: There's a small bug in the reference code - the condition nums[l] == nums[l + 1] should be nums[l] == nums[l - 1] since we're moving l leftward.

Time and Space Complexity

• Time Complexity: O(n³) - We have two nested loops for fixing the first two elements O(n²), and for each pair, we use two pointers that traverse the remaining array O(n).
• Space Complexity: O(1) if we don't count the output array, as we only use a constant amount of extra space for pointers and temporary variables.

The sorting step takes O(n log n) time, but it's dominated by the O(n³) main algorithm.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works.

Example Input:

• nums = [1, 0, -1, 0, -2, 2]
• target = 0

Step 1: Sort the array After sorting: nums = [-2, -1, 0, 0, 1, 2]

Step 2: Fix first element (i=0, nums[i]=-2)

Iteration 1.1: Fix second element (j=1, nums[j]=-1)

• First two elements: -2, -1 (sum = -3)
• Need remaining two to sum to: 0 - (-3) = 3
• Two pointers: k=2 (nums[k]=0), l=5 (nums[l]=2)
  • Sum: -2 + (-1) + 0 + 2 = -1 < 0
  • Move k right: k=3
  • Sum: -2 + (-1) + 0 + 2 = -1 < 0
  • Move k right: k=4
  • Sum: -2 + (-1) + 1 + 2 = 0 ✓ Found!
  • Add [-2, -1, 1, 2] to result
  • Move both pointers: k=5, l=4 (k >= l, stop)

Iteration 1.2: Fix second element (j=2, nums[j]=0)

• First two elements: -2, 0 (sum = -2)
• Two pointers: k=3 (nums[k]=0), l=5 (nums[l]=2)
  • Sum: -2 + 0 + 0 + 2 = 0 ✓ Found!
  • Add [-2, 0, 0, 2] to result
  • Move both pointers: k=4, l=4 (k >= l, stop)

Iteration 1.3: Fix second element (j=3, nums[j]=0)

• Skip! (nums[3] == nums[2], duplicate)

Step 3: Fix first element (i=1, nums[i]=-1)

Iteration 2.1: Fix second element (j=2, nums[j]=0)

• First two elements: -1, 0 (sum = -1)
• Two pointers: k=3 (nums[k]=0), l=5 (nums[l]=2)
  • Sum: -1 + 0 + 0 + 2 = 1 > 0
  • Move l left: l=4
  • Sum: -1 + 0 + 0 + 1 = 0 ✓ Found!
  • Add [-1, 0, 0, 1] to result
  • Move both pointers: k=4, l=3 (k >= l, stop)

Step 4: Fix first element (i=2, nums[i]=0)

• First element is 0
• No valid quadruplets found (remaining elements don't sum to target)

Step 5: Fix first element (i=3, nums[i]=0)

• Skip! (nums[3] == nums[2], duplicate)

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

The algorithm successfully finds all unique quadruplets that sum to 0, avoiding duplicates through the skip logic at each level.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n³)

The algorithm uses three nested loops:

• The outermost loop iterates through index i from 0 to n-3, which is O(n) iterations
• The second loop iterates through index j from i+1 to n-2, which is O(n) iterations in the worst case
• The innermost while loop uses two pointers k and l that move towards each other, traversing at most O(n) elements

Since these loops are nested, the overall time complexity is O(n) × O(n) × O(n) = O(n³).

The sorting operation at the beginning takes O(n log n) time, but this is dominated by the O(n³) complexity of the main algorithm.

Space Complexity: O(log n)

The space complexity comes from:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursive call stack
• The output list ans stores the results, but this is not counted as part of the space complexity since it's the required output
• The algorithm uses only a constant amount of extra variables (i, j, k, l, x), which is O(1)

Therefore, the dominant space usage is from the sorting operation, making the overall space complexity O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Calculating Sum

One critical pitfall that's often overlooked is integer overflow when calculating the sum of four numbers. In languages with fixed integer sizes, adding four large integers can cause overflow. Even in Python (which handles arbitrary precision), other languages like Java or C++ can face this issue.

Problem Example:

# Consider nums = [1000000000, 1000000000, 1000000000, 1000000000]
# target = 4000000000
# In languages with 32-bit integers, the sum would overflow
current_sum = nums[i] + nums[j] + nums[left] + nums[right]  # Potential overflow

Solution: Convert to a larger data type or use careful arithmetic:

# For languages with overflow concerns, cast to long/int64:
current_sum = long(nums[i]) + nums[j] + nums[left] + nums[right]

# Or rearrange the comparison to avoid computing the full sum:
# Instead of: sum == target
# Use: nums[left] + nums[right] == target - nums[i] - nums[j]

2. Incorrect Duplicate Skipping Logic

A very common mistake is the boundary check when skipping duplicates for the right pointer. The code shows:

while left < right and nums[right] == nums[right + 1]:  # BUG!
    right -= 1

This will cause an index out of bounds error when right is at position n-1 initially.

Correct Solution:

# Since we're moving right pointer leftward, compare with right-1
while left < right and nums[right] == nums[right - 1]:
    right -= 1

3. Missing Early Termination Optimizations

The algorithm doesn't include pruning conditions that could significantly improve performance for certain inputs:

Problem:

# The code processes all combinations even when it's impossible to reach target
for i in range(n - 3):
    # Even if nums[i] + smallest_three > target, we continue
    # Even if nums[i] + largest_three < target, we continue

Solution with Optimizations:

for i in range(n - 3):
    if i > 0 and nums[i] == nums[i - 1]:
        continue
  
    # Early termination: smallest possible sum with current i
    if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
        break  # All subsequent sums will be larger
  
    # Skip if largest possible sum with current i is too small
    if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
        continue  # Try next i
  
    for j in range(i + 1, n - 2):
        if j > i + 1 and nums[j] == nums[j - 1]:
            continue
          
        # Similar optimizations for j
        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

4. Handling Edge Cases with Target Value

The code doesn't handle edge cases where the target or array values might be negative or zero properly in terms of optimization.

Problem:

# With negative numbers, early termination logic becomes complex
# nums = [-5, -4, -3, 1, 2, 3], target = -8
# Simple min/max comparisons don't work as expected

Solution: Be careful with pruning optimizations when dealing with negative numbers, or disable them when the array contains negative values:

# Check if array has negative numbers
has_negative = nums[0] < 0

# Apply optimizations only if all numbers are non-negative
if not has_negative:
    # Apply early termination optimizations
    if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
        break