Four Sum Problem Solution with Two Pointers Approach

The Four Sum problem extends the classic Two Sum challenge by finding all unique quadruplets that sum to a target value. This solution uses sorting combined with two-pointer technique for optimal performance and clean code structure.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input array, or must we preserve it?
2. What is the expected return format for the solution? Should we return indices or values?
3. Are duplicate quadruplets allowed in the output, or should they be deduplicated?
4. What is the expected time complexity constraint? Should we aim for O(n³) or better?
5. What is the maximum size of the input array?

Restatement in my own words: Given an array of integers and a target sum, find all unique quadruplets in the array that add up to the target. A quadruplet consists of four distinct elements from the array, and we want all combinations where their sum equals the target value.

Problem details:

• Input: An integer array nums of length n and an integer target
• Output: A list of lists containing unique quadruplets that sum to target
• Constraints:
  • Array length can be up to 200 (based on typical FAANG constraints)
  • Values can range from -10⁹ to 10⁹
  • Each quadruplet must use distinct indices from the array

Assumptions I'm making:

• The input array can be modified (we can sort it)
• We want unique quadruplets (no duplicate combinations)
• The return format should be a list of lists containing the actual values, not indices
• We can use additional space for our solution

Data shape and hidden structure: This is a generalization of the classic 3Sum problem. The key insight is that we can reduce it to a 2Sum problem by fixing two elements and then solving for the remaining two. The array structure allows us to use sorting and two-pointer techniques for optimization, which is a common pattern in array-based problems involving sum constraints.

2. Pattern Recognition

The problem fits the "Two Pointers" and "Hash Map" patterns, with a strong emphasis on the "Two Pointers" approach for optimization.

The key wording that signals these patterns includes:

• "Find all unique quadruplets" - suggests we need to systematically explore combinations while avoiding duplicates
• "Return all possible combinations" - indicates a combinatorial search space that can be optimized with structured traversal
• "Sum equals target" - the classic setup for two-pointer technique when the array is sorted

This problem fits the Two Pointers pattern because:

1. We can fix two elements and use two pointers to find the remaining two elements efficiently
2. The array can be sorted to enable efficient searching with two pointers
3. The problem structure naturally allows for reducing the search space by fixing elements and using the remaining array as a two-sum problem

The core insight is that we can reduce the 4Sum problem to a series of 3Sum problems, and ultimately to 2Sum problems by fixing two elements and applying the two-pointer technique on the remaining portion of the array.

This approach leverages the fact that once we fix two numbers, we're left with a classic 2Sum problem where we can use the two-pointer technique to find pairs that sum to the remaining target value. The key is maintaining proper ordering and handling duplicates at each level of the reduction.

The pattern also involves "Sorting + Two Pointers" - a common combination for problems where we need to find combinations that sum to a target value in a way that allows us to eliminate search space systematically.

3. Approach Evolution

My first instinct is to use a two-pointer technique similar to what we'd use for 2Sum, but extended to handle multiple elements. However, that approach would be O(n³) in the worst case because we'd need to fix two elements and then use two pointers for the remaining elements. That's not optimal.

Let me think about how to optimize this. I notice that if I sort the array first, I can use a combination of fixed elements and two-pointer technique to reduce the complexity. If I fix one element, then another element, I can use two pointers to find pairs that sum to the remaining target. But wait, that's still O(n³) because I have to fix two elements.

Actually, let me reconsider the problem structure. If I sort the array first, then for each element at index i, I can use two pointers to find pairs in the remaining array that sum up to (target - nums[i]). This is O(n²) for the two-pointer search, and since I'm fixing one element at a time, that's O(n) for the outer loop. So overall it's O(n²).

But I'm not just looking for one pair - I'm looking for all combinations. So I need to be more careful about duplicates and ensure I don't double-count solutions.

The key insight is that once we fix the first element, we can apply a standard 2Sum approach on the remaining elements. But we must handle duplicates carefully - when we find a valid triplet, we need to skip over duplicate values for both the fixed element and the two-pointer elements to avoid duplicate triplets in our result.

The optimization comes from sorting first, which allows us to use two pointers instead of nested loops for finding pairs. This reduces the time complexity from O(n³) to O(n²). The space complexity remains O(1) if we don't count the output array.

Important invariants that must hold:

1. The array is sorted to enable two-pointer technique
2. When fixing the first element, we skip duplicates to avoid duplicate triplets
3. When using two pointers, we move both pointers when we find a match to avoid missing any valid combinations
4. We only add triplets to result when we have found a valid sum that matches our target

The approach is to:

1. Sort the array to enable two-pointer technique and simplify duplicate handling
2. Iterate through each element as a potential first element of the triplet
3. For each such element, use two pointers to find pairs in the remaining array that sum to (target - current_element)
4. Skip duplicates at both levels to ensure unique triplets in the result

This approach is optimal for the 3Sum problem because we can't do better than O(n²) since we might need to output all valid triplets, and there could be O(n²) such triplets in the worst case.

4. Data Structure Choice

For the 3Sum problem, I'll use a combination of data structures to achieve optimal performance:

Primary Data Structures:

1. Array/List - The input array is the primary data structure that holds our numbers. I'll use int[] for efficiency, but could also work with List<Integer> if needed for flexibility.

2. HashSet - I'll use HashSet<Integer> to store elements we've seen during the two-pointer traversal. This allows O(1) lookup time when checking if a complement exists, which is crucial for avoiding O(n²) complexity.

3. List<List> - For storing the result triplets. Each triplet is represented as List<Integer> and the outer structure holds all valid combinations.

Why These Choices:

• Array as input: Most efficient for indexed access and sorting operations. The problem constraints suggest we can modify the input array, making this acceptable.
• HashSet for lookups: Provides constant-time average lookup performance, which is essential for maintaining O(n²) overall complexity rather than O(n³). Without this optimization, we'd need to scan the remaining array for each pair, leading to quadratic time.
• List for results: Allows flexible storage of variable-length triplets and is the natural choice for returning collections in Java.

Space Impact:

• The HashSet uses O(n) space in worst case (when all elements are unique and we store many of them)
• The result list uses O(k) space where k is the number of valid triplets (bounded by O(n²) in worst case)
• Overall space complexity is O(n)

Helper Structures:

• Sorting: The array itself is sorted in-place, which enables the two-pointer technique and helps with duplicate handling
• Two pointers: No additional data structure needed beyond indices, making it memory efficient

This combination provides the best balance between time efficiency (O(n²) with HashSet lookups) and space usage (O(n) additional space), making it ideal for the constraints typically seen in FAANG interviews.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

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

Step 1: Sort the array → [-2, -1, 0, 0, 1, 2]

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

• Set left = i + 1 = 1, right = nums.length - 1 = 5
• Current sum = -2 + (-1) + 2 = -1 < target (0) → move left pointer right
• Current sum = -2 + 0 + 2 = 0 == target (0) → Found valid triplet [-2, -1, 1]
• Move left pointer right to avoid duplicates

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

• Set left = i + 1 = 2, right = nums.length - 1 = 5
• Current sum = -1 + 0 + 2 = 1 > target (0) → move right pointer left
• Current sum = -1 + 0 + 1 = 0 == target (0) → Found valid triplet [-1, 0, 1]
• Move left pointer right to avoid duplicates

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

• Set left = i + 1 = 3, right = nums.length - 1 = 5
• Current sum = 0 + 0 + 2 = 2 > target (0) → move right pointer left
• Current sum = 0 + 0 + 1 = 1 > target (0) → move right pointer left
• Current sum = 0 + 0 + 0 = 0 == target (0) → Found valid triplet [0, 0, 0]
• Move left pointer right to avoid duplicates

Step 5: Continue with remaining elements, skipping duplicates

• When nums[i] = 0 (already processed), skip to next unique element

Key invariants maintained:

1. i < left < right throughout the process
2. Array is sorted, so we can use two-pointer technique
3. Duplicates are skipped by checking nums[i] == nums[i-1] and nums[left] == nums[left-1]
4. For each fixed element, we explore all valid combinations with remaining elements

The algorithm terminates correctly because:

• We process each unique element once for the first position
• For each first element, we exhaust all valid combinations using two pointers
• We avoid duplicate triplets by skipping repeated elements in both outer and inner loops

graph TD
    A[Sort array] --> B{Fix first element}
    B --> C[Set left=first+1, right=end]
    C --> D{Sum < target?}
    D -->|Yes| E[Move left pointer right]
    D -->|No| F[Move right pointer left]
    E --> G{Sum == target?}
    F --> G
    G -->|Yes| H[Add to result]
    H --> I[Skip duplicates]
    I --> J{left < right?}
    J -->|Yes| C
    J -->|No| K[Next first element]
    K --> L{End of array?}
    L -->|No| B
    L -->|Yes| M[Return result]

6. Java Solution

import java.util.*;

public class FourSum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // Handle edge cases
        if (nums == null || nums.length < 4) {
            return new ArrayList<>();
        }
        
        // Sort the array to enable two-pointer technique and early termination
        Arrays.sort(nums);
        
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        
        // Fix first element
        for (int i = 0; i < n - 3; i++) {
            // Skip duplicates for first element
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // Fix second element
            for (int j = i + 1; j < n - 2; j++) {
                // Skip duplicates for second element
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                
                // Use two pointers for remaining two elements
                int left = j + 1;
                int right = n - 1;
                
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        // Skip duplicates for third element
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        
                        // Skip duplicates for fourth element
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++; // Need larger sum
                    } else {
                        right--; // Need smaller sum
                    }
                }
            }
        }
        
        return result;
    }
}

This solution uses a combination of sorting, nested loops with two pointers, and careful duplicate handling to efficiently find all unique quadruplets that sum to the target value. The key insight is to fix two elements and use two pointers for the remaining elements, which reduces the problem from O(n⁴) to O(n³) time complexity.

7. Complexity Analysis

Time Complexity: O(n³)

The time complexity breaks down as follows:

• Sorting the array takes O(n log n)
• The outer loop runs O(n) times
• The two-pointer inner loop runs at most O(n) times across all iterations
• Overall: O(n log n) + O(n) × O(n) = O(n²) for the nested loops, but since we're looking for 4 numbers that sum to target, and we have two nested loops, it's O(n³)

Space Complexity: O(1)

The space complexity is O(1) for the algorithm itself, excluding the space needed to store the output results. We only use a constant amount of extra space for variables like left, right, i, j, etc. The space required to store the result list is not counted in the algorithmic complexity analysis.

Why these bounds are correct:

The O(n³) time bound is tight because:

1. We must examine all possible combinations of 4 elements to ensure we don't miss any valid quadruplets
2. The two-pointer technique reduces the inner search from O(n²) to O(n), but we still need to iterate through all pairs of the first two elements
3. For each pair, we do linear work to find valid combinations using two pointers

Optimality:

This is near-optimal for the general case. The problem requires finding all unique quadruplets that sum to a target, which inherently needs to examine many combinations. Any algorithm that finds all valid solutions must have at least O(n³) time complexity in the worst case, since there could be O(n³) valid solutions (e.g., when many combinations sum to the target). The solution achieves this lower bound by using the two-pointer technique to efficiently prune search space while maintaining correctness.

8. Edge Cases & Pitfalls

The most common edge cases and implementation pitfalls for 4Sum (and related kSum problems) include:

Empty and minimal inputs:

• Empty array should return empty result list
• Arrays with fewer than 4 elements should return empty result
• Single element or two elements arrays should return empty result

Duplicate handling:

• The solution must avoid duplicate quadruplets in the output
• When using sorting and two pointers, duplicates can be skipped by checking nums[i] == nums[i-1] for the first element and similar checks for subsequent elements
• Without proper duplicate handling, solutions may return multiple copies of the same quadruplet

Boundary conditions:

• When target is very large or very small, the algorithm should still work correctly
• Integer overflow when computing sums (though less likely in 4Sum with typical constraints)
• Arrays that are already sorted or reverse sorted

Common implementation mistakes:

1. Incorrect loop bounds: Not properly limiting the outer loops to avoid index out of bounds errors
2. Missing duplicate skips: Failing to skip over duplicate values in the inner loops, leading to incorrect results
3. Wrong termination conditions: Not accounting for proper early termination when remaining elements are insufficient to form a valid quadruplet
4. Not handling negative numbers properly: The two-pointer technique requires sorted arrays, but the approach must work with mixed positive/negative numbers
5. Incorrect result formatting: Adding null or empty lists to the result when they shouldn't be included

Performance edge cases:

• Arrays with many duplicate elements can cause performance degradation if not handled properly
• Very large arrays with no valid solutions should terminate efficiently rather than process all combinations

The key to avoiding these pitfalls is careful boundary checking, proper duplicate handling logic, and thorough testing with edge case inputs.

9. Alternative Approaches

There are several alternative approaches to solving the 4Sum problem, each with different trade-offs:

Approach 1: Brute Force with HashSet Instead of sorting, we could use a HashSet to store intermediate sums and check for complement values. This would require O(n⁴) time complexity in the worst case due to nested loops, but could be optimized with early termination conditions. This approach is less efficient than our two-pointer solution and doesn't leverage the sorted structure.

Approach 2: Recursive K-Sum Solution We could implement a generic k-sum solution that recursively reduces to 2Sum. For 4Sum, this would involve:

1. Fixing two elements
2. Solving 2Sum for the remaining two elements using two pointers
3. This approach has O(n^(k-1)) time complexity where k=4, so O(n³)
4. It's more generic but adds recursive overhead and complexity

Approach 3: Hash Map Based Approach Use hash maps to store sums of pairs and their indices. For each pair, check if the complement exists in our hash map. This approach has O(n²) time complexity for building the map and O(n²) for lookup, but requires O(n²) space. It's more complex to implement correctly and has higher space overhead.

Comparison with Main Solution: Our chosen two-pointer approach is optimal for time complexity (O(n³)) and provides better space efficiency (O(1) additional space). The recursive approach offers more flexibility for generalization but adds unnecessary complexity for the specific 4Sum case. The hash map approach trades space efficiency for a different time complexity structure.

The main solution is preferred because it's more intuitive, has optimal time complexity, and uses minimal additional space while maintaining clean code structure.

10. Test Cases

public class FourSumTestCases {
    public static void main(String[] args) {
        // Test Case 1: Basic case with multiple solutions
        int[] nums1 = {1, 0, -1, 0, -2, 2};
        int target1 = 0;
        // Expected: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
        
        // Test Case 2: Empty array
        int[] nums2 = {};
        int target2 = 0;
        // Expected: []
        
        // Test Case 3: Single element array
        int[] nums3 = {1};
        int target3 = 0;
        // Expected: []
        
        // Test Case 4: All same elements
        int[] nums4 = {2, 2, 2, 2};
        int target4 = 8;
        // Expected: [[2, 2, 2, 2]]
        
        // Test Case 5: No valid combinations
        int[] nums5 = {1, 2, 3, 4};
        int target5 = 10;
        // Expected: []
        
        // Test Case 6: Negative target
        int[] nums6 = {1, -2, 3, -1};
        int target6 = -1;
        // Expected: [[-2, -1, 1, 3]]
        
        // Test Case 7: Large numbers
        int[] nums7 = {1000000000, 1000000000, 1000000000, 1000000000};
        int target7 = 4000000000L;
        // Expected: [[1000000000, 1000000000, 1000000000, 1000000000]]
        
        // Test Case 8: Mixed positive and negative
        int[] nums8 = {-1, 0, 1, 2, -1, -4};
        int target8 = 0;
        // Expected: [[-1, -1, 0, 2], [-1, 0, 0, 1]]
    }
}

Sample Test Cases:

Basic case with multiple solutions:

• Input: nums = [1, 0, -1, 0, -2, 2], target = 0
• Expected: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Edge case - Empty array:

• Input: nums = [], target = 0
• Expected: []

Edge case - Single element:

• Input: nums = [1], target = 0
• Expected: []

Edge case - All same elements:

• Input: nums = [2, 2, 2, 2], target = 8
• Expected: [[2, 2, 2, 2]]

Tricky case - No valid combinations:

• Input: nums = [1, 2, 3, 4], target = 10
• Expected: []

Boundary case - Negative target:

• Input: nums = [1, -2, 3, -1], target = -1
• Expected: [[-2, -1, 1, 3]]

11. Final Summary

The core insight is to reduce the k-sum problem to a simpler 2-sum problem by fixing the first k-2 elements and using two pointers for the remaining two elements. This approach efficiently handles duplicates by skipping over repeated values and maintains O(n²) time complexity for the 4-sum case while using O(1) extra space (excluding output storage). The solution works by leveraging the sorted array structure to enable efficient two-pointer traversal, making it both optimal and practical for real-world applications where memory and performance are constrained.