4 sum

18.4Sum

Array

Two Pointers

Sorting

Hash Table

Problem Statement:

Given an array nums of n integers and an integer target, find all unique quadruplets in the array that sum to the target value. The solution set must not contain duplicate quadruplets.

Example:

Input:

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

→

Output:

[[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]

Algorithm:

1. Sort array for two-pointer approach
2. Use nested loops for first two numbers
3. Use two pointers for remaining sum
4. Skip duplicates using Set

Complexity:

Time: O(n³) | Space: O(1)

Java Solution:

public ListInteger>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);  // Sort for two-pointer approach
    SetInteger>> result = new HashSet<>();
    
    for (int i = 0; i < nums.length - 3; i++) {
        for (int j = i + 1; j < nums.length - 2; j++) {
            int k = j + 1;
            int l = nums.length - 1;
            
            while (k < l) {
                int sum = nums[i] + nums[j] + nums[k] + nums[l];

                if (sum < target) {
                    k++;  // Increase sum by moving left pointer
                } else if (sum > target) {
                    l--;  // Decrease sum by moving right pointer
                } else {
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k], nums[l])));
                    k++;
                    l--;  // Continue searching for more quadruplets
                }
            }
        }
    }
    
    return new ArrayList<>(result);
}

Python Solution:

def fourSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    result = set()
    
    for i in range(len(nums) - 3):
        for j in range(i + 1, len(nums) - 2):
            k = j + 1
            l = len(nums) - 1
            
            while k < l:
                curr_sum = nums[i] + nums[j] + nums[k] + nums[l]
                
                if curr_sum < target:
                    k += 1
                elif curr_sum > target:
                    l -= 1
                else:
                    result.add((nums[i], nums[j], nums[k], nums[l]))
                    k += 1
                    l -= 1
    
    return [list(x) for x in result]

C++ Solution:

class Solution {
public:
    vectorint>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        setint>> result;
        
        for (int i = 0; i < nums.size() - 3; i++) {
            for (int j = i + 1; j < nums.size() - 2; j++) {
                int k = j + 1;
                int l = nums.size() - 1;
                
                while (k < l) {
                    long sum = (long)nums[i] + nums[j] + nums[k] + nums[l];
                    
                    if (sum < target) {
                        k++;
                    } else if (sum > target) {
                        l--;
                    } else {
                        result.insert({nums[i], nums[j], nums[k], nums[l]});
                        k++;
                        l--;
                    }
                }
            }
        }
        
        return vectorint>>(result.begin(), result.end());
    }
};