4Sum

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Goldman Sachs
Array Hash Two PointerViews 2297

In the 4Sum problem, we have given an integer x and an array a[ ] of size n. Find all the unique set of 4 elements in array such that sum of those 4 elements is equal to the given integer x.

4Sum

Example

Input 

a[ ] = {1, 0, -1, 0, -2, 2}

x = 0

Output 

1, 0, -1, 0
1, -1, -2, 2
0, 0, -2, 2

Input 

a[ ] = {1, 2, 4, 3, -3, 0, -2}

x = 7

Output 

1, 2, 4, 0
2, 4, 3, -2

Naive Method

Algorithm for 4Sum

  1. Initialize an array a[ ] of size n and an integer x.
  2. Traverse four-loop with the first loop starting from 0 to n-4 and rest three inner loops starting from the value of its outer loop + 1 till n-3, n-2 and n-1 respectively.
  3. Check if the sum of elements at all four indexes is equal to the given integer, print all four elements.

Time Complexity: O(n4) because we are check for four values and for each value we use one loop for find its all ways of selection.

Auxiliary Space: O(1) because we don’t use any auxiliary space in the implementation part.

C++ Program to find 4Sum

#include <bits/stdc++.h> 
using namespace std; 
  
void fourSum(int a[], int n, int x){ 
    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 l = k+1; l < n; l++){ 
                    if(a[i] + a[j] + a[k] + a[l] == x){ 
                        cout<<a[i]<<", "<<a[j]<<", "<<a[k]<<", "<<a[l]<<endl;
                    }    
                }         
            }  
        } 
    } 
} 

int main(){
    int a[] = {1, 0, -1, 0, -2, 2}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int x = 0; 
    
    fourSum(a, n, x);
    
    return 0; 
}
1, 0, -1, 0
1, -1, -2, 2
0, 0, -2, 2

Java Program to find 4Sum

class FourElementsSum{ 
  
    void fourSum(int a[], int n, int x){ 
        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 l = k+1; l < n; l++){ 
                        if(a[i] + a[j] + a[k] + a[l] == x){  
                            System.out.print(a[i]+", "+a[j]+", "+a[k]+", "+a[l]);
                            System.out.println();
                        }    
                    } 
                } 
            } 
        } 
    } 
  
    public static void main(String[] args){ 
        FourElementsSum f = new FourElementsSum(); 
        
        int a[] = {1, 0, -1, 0, -2, 2}; 
        int n = a.length; 
        int x = 0; 
        
        f.fourSum(a, n, x); 
    } 
}
1, 0, -1, 0
1, -1, -2, 2
0, 0, -2, 2

Using Sorting Method

Algorithm

  1. Initialize an array a[ ] of size n and an integer x.
  2. Sort the array using quicksort.
  3. Set the first element by traversing from 0 to n-4 and second element by traversing from Outer loop+1 to n-3.
  4. Set elements 3 and 4 as j+1 and element 4 as n-1.
  5. Traverse while the third element is less than fourth.
  6. Check if sum of these four elements is equal to a given integer, print the four elements, and increment the third element and decrement the fourth element.
  7. Else if the sum of these four elements is less than given integer, increment the third element.
  8. Else decrement the fourth element.

Time Complexity: O(n3) where n denotes the number of elements present in the input array.

Auxiliary Space: O(1) because here we don’t use any auxiliary space.

C++ Program to find 4Sum

#include <bits/stdc++.h> 
using namespace std; 
  
int compare(const void *a, const void * b){  
    return( *(int *)a - *(int *)b );  
}  
  
void fourSum(int a[], int n, int x){ 
    int l, r;  
  
    qsort(a, n, sizeof(a[0]), compare);  
  
    for(int i = 0; i < n-3; i++){
        
        for(int j = i+1; j < n-2; j++){  
            
            l = j+1;  
            r = n-1;  
  
            while(l < r){  
                if(a[i] + a[j] + a[l] + a[r] == x){  
                    cout<<a[i]<<", "<<a[j]<<", "<<a[l]<<", "<<a[r]<<endl;  
                    l++; 
                    r--;  
                }  
                
                else if(a[i] + a[j] + a[l] + a[r] < x){  
                    l++;  
                }    
                else{  
                    r--;
                }    
            } 
        } 
    } 
} 

int main(){
    int a[] = {1, 0, -1, 0, -2, 2}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int x = 0; 
    
    fourSum(a, n, x);
    
    return 0; 
}
-2, -1, 1, 2
-2, 0, 0, 2
-1, 0, 0, 1

Java Program to find 4Sum

import java.util.Arrays;

class FourElementsSum{ 
  
    void fourSum(int a[], int n, int x){ 
        int l, r; 
  
        Arrays.sort(a); 
  
        for(int i = 0; i < n-3; i++){
            
            for(int j = i+1; j < n-2; j++){ 
                l = j+1; 
                r = n-1; 
  
                while(l < r){ 
                    if(a[i] + a[j] + a[l] + a[r] == x){ 
                        System.out.println(a[i]+", "+a[j]+", "+a[l]+", "+a[r]); 
                        l++; 
                        r--; 
                    }  
                    
                    else if(a[i] + a[j] + a[l] + a[r] < x) 
                        l++; 
                    else{
                        r--;
                    }    
                } 
            } 
        } 
    }  
  
    public static void main(String[] args){ 
        FourElementsSum f = new FourElementsSum(); 
        
        int a[] = {1, 0, -1, 0, -2, 2}; 
        int n = a.length; 
        int x = 0; 
        
        f.fourSum(a, n, x); 
    } 
}
-2, -1, 1, 2
-2, 0, 0, 2
-1, 0, 0, 1

More Efficient Method

Algorithm

  1. Initialize a vector a[ ] of size n and an integer x.
  2. Create a 2D vector ans to store the result and an unordered map.
  3. Traverse through the vector and store the sum of all combinations in map.
  4. Search the target-sum in map.
  5. Create a vector of pair type of int, int and update it as map[target-sum].
  6. Traverse pair vector and initialise a new vector in it..
  7. Store the four chosen elements in this new vector.
  8. Sort the new vector.
  9. Check if sum of these four elements is equal and elements are not common either, push the elements in 2D vector ans.
  10. Print the 2D vector for the result.

Time Complexity: O(n2) where n denotes the number of elements in the given vector a.

Auxiliary Space: O(n2) because here we use n2 auxiliary space in vectors and hashmaps.

C++ Program to find 4Sum

#include <bits/stdc++.h> 
using namespace std; 
  
class FourElementsSum{
    public:
    
        bool notCommon(pair<int,int> p1,pair<int,int> p2){
            if(p1.first!=p1.second && p2.first!=p1.second && p2.first!=p2.second && p1.first!=p2.second && p1.first!=p2.first && p1.second!=p2.second)
                return true;
            return false;
        }
        
        void fourSum(vector<int>& nums, int target){
            vector<vector<int>> ans;
            
            if(nums.size()<4)
                cout<<"Size is less than 4";
            
            unordered_map<int,vector<pair<int,int>> > m;
            
            for(int i=0; i<nums.size()-1; i++){
                for(int j=i+1; j<nums.size(); j++){
                    m[nums[i]+nums[j]].push_back(make_pair(i,j));
                }
            }    
         
            for(int i=0; i<nums.size(); i++){
                for(int j=i+1; j<nums.size(); j++){
                    int sum=nums[i]+nums[j];
                    if(m.find(target-sum)!=m.end()){
                        
                        vector<pair<int,int>> p=m[target-sum];
                        
                        for(int k=0;k<p.size();k++){
                            vector<int> v;
                            v.push_back(nums[i]);
                            v.push_back(nums[j]);
                            v.push_back(nums[m[target-sum][k].first]);
                            v.push_back(nums[m[target-sum][k].second]);
                            sort(v.begin(),v.end());
                            if(find(ans.begin(),ans.end(),v)==ans.end()&& notCommon(make_pair(i,j),m[target-sum][k])  )
                            ans.push_back(v);
                        }
                    }
                }
            }
            
            for (int i = 0; i < ans.size(); i++) {
                for (int j = 0; j < ans[i].size(); j++){ 
                    cout << ans[i][j] << " ";
                }    
                cout << endl; 
            }     
        }    
};

int main(){
    FourElementsSum f;
    vector<int> a = {1, 0, -1, 0, -2, 2}; 
    int x = 0;
 
    f.fourSum(a, x);
    
    return 0; 
}
-1 0 0 1 
-2 -1 1 2 
-2 0 0 2

References

Translate »