Efficient Four Sum Problem Solution with Two-Pointer Approach

content:

The Four Sum problem challenges you to find all unique quadruplets in an array that sum to a target value. After solving Two Sum and Three Sum variations, this DSA question builds on similar principles but requires careful handling of duplicates. In analyzing this coding tutorial, I'll share an optimized approach that reduces duplicates while maintaining O(n³) time complexity – crucial for technical interviews.

Understanding the Four Sum Problem

Given an unsorted integer array and a target value, identify all unique sets of four distinct elements where nums[i] + nums[j] + nums[k] + nums[l] = target. LeetCode 18 specifies quadruplets must use distinct indices, and solutions must avoid duplicate combinations. Consider the sorted array [-2, -1, 0, 1, 2] with target 0: valid quadruplets include [-2, -1, 1, 2] and [-1, 0, 0, 1] (if duplicates exist).

Critical constraints:

1. Indices i, j, k, l must be distinct
2. Solutions must return unique quadruplets
3. Optimal solutions avoid O(n⁴) brute-force approaches

Step-by-Step Solution Methodology

First, sort the array to enable pointer manipulation. Sorting allows efficient two-pointer techniques and duplicate detection – the foundation of our optimization. For example, sorting [1, -1, 2, -2] becomes [-2, -1, 1, 2].

Nested loop structure:

1. Outer loop (i from 0 to n-3) selects first element
2. Inner loop (j from i+1 to n-2) selects second element
3. Initialize pointers p = j + 1 (smallest remaining) and q = n - 1 (largest remaining)

nums.sort()
quadruplets = []
n = len(nums)

for i in range(n-3):
    # Optimization 1: Skip duplicate i-values
    if i > 0 and nums[i] == nums[i-1]:
        continue
        
    for j in range(i+1, n-2):
        # Optimization 2: Skip duplicate j-values
        if j > i+1 and nums[j] == nums[j-1]:
            continue
        p, q = j+1, n-1

Two-pointer adjustment:

• Calculate current sum S = nums[i] + nums[j] + nums[p] + nums[q]
• If S < target: increment p (increase sum)
• If S > target: decrement q (decrease sum)
• If S == target: record quadruplet and move both pointers

while p < q:
    current_sum = nums[i] + nums[j] + nums[p] + nums[q]
    if current_sum < target:
        p += 1
    elif current_sum > target:
        q -= 1
    else:
        quadruplets.append([nums[i], nums[j], nums[p], nums[q]])
        p += 1
        q -= 1
        # Optimization 3: Skip duplicate p-values
        while p < q and nums[p] == nums[p-1]:
            p += 1

Practical pitfalls:

• Forgetting to sort causes two-pointer failure
• Skipping p duplicates but not q still causes duplicates – q deduplication is implicit
• Integer overflow with large targets requires long in some languages

Key Optimizations and Complexity Analysis

Three strategic optimizations prevent duplicate quadruplets:

1. Skip duplicate i values: After processing nums[i], advance i past identical values
2. Skip duplicate j values: Within fixed i, skip j duplicates after first occurrence
3. Skip duplicate p values: After finding a valid quadruplet, advance p past duplicates

Time complexity:

• Sorting: O(n log n)
• Nested loops: O(n³) worst-case (outer loop O(n), inner loops O(n), two-pointer O(n))
• Total: O(n³) – optimal for this problem

Space complexity: O(1) auxiliary space (ignoring output storage), as operations happen in-place.

Why this outperforms hashing:

• Avoids hash collision overhead
• Eliminates need for duplicate tracking sets
• More cache-friendly with sorted data

Implementation Checklist

Apply these steps in your solution:

1. Sort input array
2. Iterate i from 0 to n-4
3. Skip nums[i] if duplicate of previous
4. Iterate j from i+1 to n-3
5. Skip nums[j] if duplicate
6. Set p = j+1, q = n-1
7. While p < q:
   • Calculate current sum
   • Adjust pointers based on sum vs target
   • Record matches and skip duplicate p values
8. Return collected quadruplets

Recommended resources:

• Book: "The Algorithm Design Manual" by Skiena (comprehensive DSA strategies)
• Practice: LeetCode’s "4Sum" follow-ups - 4Sum II and K-Sum
• Tool: VisuAlgo.net for sorting/pointer visualization (ideal for beginners)

Which optimization step do you find most challenging to implement? Share your experience in the comments – I’ll address common pitfalls in a follow-up guide. Mastering this pattern unlocks more complex problems like partition arrays and subset sums.