4Sum [Medium] — Sort + Two Pointers

Problem Statement

Given an array, return all unique quadruplets [a,b,c,d] where a+b+c+d == target.

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

Intuition

Sort + two outer loops (indices i, j) + two-pointer inner loop (left, right). Skip duplicates at all four levels.

Solutions

C++

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i=0;i<n-3;i++){
        if(i>0&&nums[i]==nums[i-1]) continue;
        for(int j=i+1;j<n-2;j++){
            if(j>i+1&&nums[j]==nums[j-1]) continue;
            int l=j+1, r=n-1;
            while(l<r){
                long sum=(long)nums[i]+nums[j]+nums[l]+nums[r];
                if(sum==target){
                    res.push_back({nums[i],nums[j],nums[l++],nums[r--]});
                    while(l<r&&nums[l]==nums[l-1])l++;
                    while(l<r&&nums[r]==nums[r+1])r--;
                } else if(sum<target) l++;
                else r--;
            }
        }
    }
    return res;
}

Python

def fourSum(nums: list[int], target: int) -> list[list[int]]:
    nums.sort()
    res, n = [], len(nums)
    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
            l, r = j+1, n-1
            while l < r:
                s = nums[i]+nums[j]+nums[l]+nums[r]
                if s == target:
                    res.append([nums[i],nums[j],nums[l],nums[r]])
                    while l < r and nums[l] == nums[l+1]: l += 1
                    while l < r and nums[r] == nums[r-1]: r -= 1
                    l += 1; r -= 1
                elif s < target: l += 1
                else: r -= 1
    return res

Complexity

Time: O(n³)
Space: O(1) (output excluded)