4Sum Problem Solution [Leetcode]

4Sum Problem: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • abc, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example :

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

4Sum Problem Solution [Leetcode]

Problem Solution In Python

from typing import List


class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []

        def k_sum(nums, k, target, arr, start_idx):
            if k == 2:
                two_sum(nums, arr, k, start_idx, target)
                return
            for i in range(start_idx, len(nums) - k + 1):
                if i > start_idx and nums[i] == nums[i - 1]:
                    continue
                k_sum(nums, k - 1, target - nums[i], arr + [nums[i]], i + 1)

        def two_sum(nums, arr, k, start_idx, target):
            left = start_idx
            right = len(nums) - 1

            while left < right:
                total = nums[left] + nums[right]
                if total == target:
                    res.append(arr + [nums[left], nums[right]])
                    left += 1
                    right -= 1

                    while left < right and nums[left] == nums[left - 1]:
                        left += 1  # skip same element to avoid duplicate quadruplets
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1  # skip same element to avoid duplicate quadruplets
                elif total < target:
                    left += 1
                else:
                    right -= 1

        k_sum(nums, 4, target, [], 0)
        return res

Problem Solution In Java

public List<List<Integer>> fourSum(int[] nums, int target) {
    
    int n = nums.length;
    List<List<Integer>> res = new ArrayList();
    
    for(int i = 0; i < n-3; i++){
        
        for(int j = i+1; j < n-2; j++){
            
            for(int k = j+1; k < n-1; k++){
                
                for(int t = k+1; t < n; t++){
                    
                    if(nums[i]+nums[j]+nums[k]+nums[t] == target){
                        
                        int[] arr = new int[]{nums[i], nums[j], nums[k], nums[t]};
                        Arrays.sort(arr);
                        
                        if(!contains(arr, res)){
                            res.add(Arrays.asList(arr[0], arr[1], arr[2], arr[3]));
                        }                            
                    }
                }
            }                
        }            
    }
    
    return res;
}

boolean contains(int[] arr, List<List<Integer>> res){
    
    for(List<Integer> itr: res){
        if(itr.get(0) == arr[0] && itr.get(1) == arr[1] && itr.get(2) == arr[2] && itr.get(3) == arr[3])
            return true;
    }
    
    return false;
}

Problem Solution In C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>>ans1;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            for(int j=i+1;j<n-2;j++)
            {
                int left=j+1;
                int right=n-1;
                while(left<right)
                {
                    int sum1=nums[i]+nums[j];
                    int sum2=target-(nums[left]+nums[right]);
                    if(sum2<sum1)
                    {
                        right--;
                    }
                    else if(sum1==sum2)
                    {
                        vector<int>v{nums[i],nums[j],nums[left],nums[right]};
                        ans1.insert(v);
                        left++;
                    }
                    else
                    {
                        left++;
                    }
                }
            }
        }
        vector<vector<int>>ans(ans1.begin(),ans1.end());
        return ans;
    }
};

Problem Solution In C

int cmp(const void *a,const void *b){
    return *(int *)a-*(int *)b;
}
int** fourSum(int* nums, int len, int target, int* returnSize, int** returnColumnSizes){
    if(len<4){
        *returnColumnSizes=NULL;
        *returnSize=0;
        return NULL;
    }
    qsort(nums,len,sizeof(int),cmp);
    int cnt=0;
    int base=8;
    int **ans=malloc(sizeof(int *)*8);
    int sum;
    int l,r;
    for(int i=0;i<len-3;i++){
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }
        if(nums[i]*4>target){
            break;
        }
        for(int j=i+1;j<len-2;j++){
            if(j>i+1&&nums[j]==nums[j-1]){
                continue;
            }
            if(nums[j]*3+nums[i]>target||nums[len-1]*3+nums[i]<target){
                break;
            }
            l=j+1;
            r=len-1;
            while(l<r){
                sum=nums[i]+nums[j]+nums[l]+nums[r];
                if(sum==target){
                    ans[cnt]=malloc(sizeof(int)*4);
                    ans[cnt][0]=nums[i];
                    ans[cnt][1]=nums[j];
                    ans[cnt][2]=nums[l];
                    ans[cnt][3]=nums[r];
                    cnt++;
                    if(cnt==base){
                        base*=2;
                        ans=realloc(ans,sizeof(int *)*base);
                    }
                    while(l<r&&nums[l]==nums[l+1]){
                        l++;
                    }
                    while(l<r&&nums[r]==nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }
                else if(sum>target){
                    r--;
                }
                else{
                    l++;
                }
            }
        }
    }
    *returnColumnSizes=malloc(sizeof(int)*cnt);
    for(int i=0;i<cnt;i++){
        (*returnColumnSizes)[i]=4;
    }
    *returnSize=cnt;
    return ans;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment