About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

4 Sum

4 Sum Problem Statement:

Given a list of numbers, find all the unique quadruples that sum up to a given target value.

Example


{
"arr": [0, 0, 1, 3, 2, -1],
"target": 3
}

Output:


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

Notes

  • Two quadruples are considered different if there exists a number whose frequencies differ in those two quadruples.
  • The quadruples can be returned in any order.
  • The order of numbers inside any quadruple does not matter.

Constraints

  • 1 <= size of the input list <= 300
  • -105 <= any element of the input list <= 105
  • -4 * 105 <= target value <= 4 * 105 

We provided four solutions for this 4 Sum problem.

Throughout this editorial, we will refer to the input array as arr, its size as n, and the target sum as target.

4 Sum Solution 1: Brute Force

A brute force solution you might think of right away is running four nested loops and checking the sum of each quadruple present in the array. If the quadruple sums up to target, then we will append it to the result.

But if duplicate elements are present in the array, this simple approach might also generate some duplicate quadruples. One way to deal with this is to maintain a set of quadruples and insert each quadruple in the sorted form in this set. 

Finally, we can simply extract the quadruples from this set, insert them into the result and return it. However, this would cost us both extra space and time.

In this 4 Sum solution, we will discuss an approach that would not require the use of a set to avoid duplication.

We will initially sort the array so that all of the duplicate occurrences of any element are adjacent to each other. The reason for this will become more clear as we move ahead.

Next, we will run four nested loops where the purpose of each loop is described below:

  • The outermost loop will fix an element arr[i] so that the three nested inner loops can find the triplets with a sum equal to (target - arr[i]).
  • The second loop will fix an element arr[j] ahead of the index i so that the two nested inner loops can find the pairs with a sum equal to (target - arr[i] - arr[j]).
  • The third loop will fix an element arr[k] ahead of the index j so that the next inner loop could find the numbers equal to (target - arr[i] - arr[j] - arr[k]).
  • The innermost loop will find an element arr[l] ahead of the index k such that (arr[i] + arr[j] + arr[k] + arr[l]) equals target.

Now, an observation here that will help us avoid the duplicate quadruples is that if the outermost loop has already considered the possibility of arr[i] being the first element of any quadruple, then any duplicate occurrences of arr[i] need not be considered again for being the first element of any other quadruple. 

Let us understand this with an example.

Say, we have arr = [0, 0, 1, 2, 3, 4, 5] and target = 10.

Now, if we consider the possibility of arr[0] being the first element of a quadruple, then the inner three loops will get us all the unique triplets with a sum equal to (10 - arr[0]) = 10.

All such unique triplets are: [1, 4, 5], [2, 3, 5].

Appending arr[0] = 0 at the beginning of all these triplets, we will get the quadruples having the first element equal to arr[0]. All such quadruples are: [0, 1, 4, 5], [0, 2, 3, 5].

Now, say we are considering the possibility of arr[1] being the first element of a quadruple. We will first call the inner three loops to get us all of the unique triplets with a sum equal to (10 - arr[1]) = 10.

Now, since arr[0] equals arr[1], the inner 3 loops will again return the following triplets: [1, 4, 5] and [2, 3, 5]. Now, if we will append arr[1] = 0 at the beginning of these triplets, it will get us the same quadruples as we got above.

The above analysis leads us to a lesson that if an element arr[i] has already been considered for being the first element of a quadruple, then any duplicate occurrence of arr[i] should not be considered for being the first element of a quadruple.

Similarly, if an element arr[j] has already been considered to be the second element of a quadruple, then any duplicate occurrence of arr[j] should not be considered for being the second element of a quadruple.

Similarly, the same can be said for the third and fourth elements of a quadruple.

Learn how you can divide two subsequences with equal sums by solving the Equal Subset Sum Partition Problem.

Time Complexity

O(n^4): We will run four nested loops on the input array of size n.

Auxiliary Space Used

O(1): We used only a constant amount of extra space.

Space Complexity

O(n^4)

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(n^4) (In the worst case, there can be O(n^4) number of output quadruples each of size 4).

So, the total space complexity is O(n^4).

Code for 4 Sum Solution 1: Brute Force



/*
Asymptotic complexity in terms of the length of input list `n`:
* Time: O(n^4).
* Auxiliary space: O(1).
* Total space: O(n^4).
*/
vector> four_sum(vector &arr, int target) {

   int n = arr.size();

   vector> result;

   sort(arr.begin(), arr.end());

   for (int i = 0; i < n; i++) {

       // If number = arr[i] has previously been used as the first element of any


       // quadruple, we skip it to avoid duplicate quadruples.


       if (i > 0 and arr[i] == arr[i - 1]) {

           continue;

       }

       for (int j = i + 1; j < n; j++) {


           // If number = arr[j] has previously been used as a second element of any


           // quadruple, we skip it to avoid duplicate quadruples.


           if (j > i + 1 and arr[j] == arr[j - 1]) {


               continue;

           }

           for (int k = j + 1; k < n; k++) {


               // If number = arr[k] has previously been used as a third element of any


               // quadruple, we skip it to avoid duplicate quadruples.


               if (k > j + 1 and arr[k] == arr[k - 1]) {


                   continue;


               }

               for (int l = k + 1; l < n; l++) {


                   // If number = arr[l] has previously been used as a fourth element of any


                   // quadruple, we skip it to avoid duplicate quadruples.


                   if (l > k + 1 and arr[l] == arr[l - 1]) {


                       continue;


                   }

                   if (arr[i] + arr[j] + arr[k] + arr[l] == target) {


                       result.push_back({ arr[i], arr[j], arr[k], arr[l] });


                   }


               }


           }


       }


   }

   return result;


}

Learn how you can solve 3 Sum Problem.

4 Sum Solution 2: Two Pointer

Given a sorted array nums of size m, we can find all the unique pairs with a sum equal to any number k in O(m) amount of time. The approach for the same is given below:

  1. Initialize the iterators low = (starting index of nums) and high = (ending index of nums).
  2. Initiate a process that runs until the condition low < high is satisfied. The approach followed by the process is:
    i) If nums[low] + nums[high] equals k: It means we have found a pair with the required sum. Therefore, we will store the pair, increment low and decrement high.
    ii) If nums[low] + nums[high] is greater than k: In this case, we are in search of a sum that is less than the current sum. To resolve this issue, we will decrement high. Since nums is sorted, decrementing high will give us a sum less than or equal to the current sum.
    iii) If nums[low] + nums[high] is less than k: In this case, we are in search of a sum that is greater than the current sum. To resolve this issue, we will increment low. Since nums is sorted, incrementing low will give us a sum greater than or equal to the current sum.
    iv) Next, we need to make sure that the duplicate pairs do not get inserted into our result. To do this, we will skip the duplicate occurrences of arr[low] and arr[high] (if any).

In the previous 4 Sum solution, the inner two loops were responsible for getting us all the unique pairs with a sum equal to (target - arr[k] - arr[l]) in O(n^2) amount of time.

In this 4 Sum solution, we will replace those two inner loops with the two-pointer-based approach discussed above.

Time Complexity

O(n3): We have two outer nested loops and then an O(n) time-taking two-pointer based approach. Therefore, the total time complexity is O(n^2 * n).

Since the output array will have a size equal to O(n^4), printing or generating it will take O(n^4) amount of time. Apart from that, the time taken by the four_sum function will be O(n^3).

Auxiliary Space Used

O(1): We used only a constant amount of extra space.

Space Complexity

O(n^4)

Space used for input: O(n).

Auxiliary space used: O(1).

Space used for output: O(n^4) (In the worst case, there can be O(n^4) number of output quadruples each of size 4).

So, the total space complexity is O(n^4).

Code for 4 Sum Solution 2: Two Pointer



/*

Asymptotic complexity in terms of the length of input list `n`:


* Time: O(n^3).


* Auxiliary space: O(1).

* Total space: O(n^4).

*/

vector> four_sum(vector &arr, int target) {

   int n = arr.size();

   vector> result;

   sort(arr.begin(), arr.end());

   for (int i = 0; i < n; i++) {


       // If number = arr[i] has previously been used as a first element of any


       // quadruple, we skip it to avoid duplicate quadruples.

       if (i > 0 and arr[i] == arr[i - 1]) {

           continue;
       }

       for (int j = i + 1; j < n; j++) {


           // If number = arr[j] has previously been used as a second element of any


           // quadruple, we skip it to avoid duplicate quadruples.


           if (j > i + 1 and arr[j] == arr[j - 1]) {


               continue;

           }

           // Following a two-pointer based approach to find all distinct pairs with


           // sum = target - (arr[i] + arr[j]) in arr[j + 1 .... n - 1].


           int low = j + 1, high = n - 1;


           while (low < high) {


               if (arr[low] + arr[high] == target - (arr[i] + arr[j])) {


                   result.push_back({ arr[i], arr[j], arr[low], arr[high] });


                   low++;


                   high--;


               }


               else if (arr[low] + arr[high] > target - (arr[i] + arr[j])) {


                   high--;


               }


               else {


                   low++;


               }

               // Skipping the duplicate occurrences of arr[low].


               if (low > j + 1) {


                   while (low <= high and arr[low] == arr[low - 1]) {


                       low++;


                   }


               }

               // Skipping the duplicate occurrences of arr[high].


               if (high < n - 1) {


                   while (high >= low and arr[high] == arr[high + 1]) {


                       high--;


                   }


               }


           }


       }


   }

   return result;

}

Learn how can you find 2 Sum in a Sorted Array problem.

4 Sum Solution 3: Two-Pointer Generic K Sum

If you are asked the “4 Sum” problem in a technical interview, it is quite possible that the interviewer will ask you to extend your solution to “5 Sum,” “6 Sum,” or a generic “K Sum” solution.

Here, we will discuss a generalized implementation of this problem.

We will follow a very similar approach that we followed in the two-pointer-based approach above.

We will initially sort the array and call the function called k_sum with the value of k equal to 4 to get us all the unique sets of size 4 with a sum of the values equal to the given target.

The approach that we will follow for the k_sum function is described below:

  1. This function will take the input array arr, the current_target, the starting index start of arr, and the value of k as its inputs. The current_target will initially be equal to the given target value, and the start will be equal to 0. The function will return all the distinct sets of size k such that they sum up to the current_target.
  2. We will then check for the following base cases:
    i) If start + k > n: It means that there are not enough elements present in the array to form a set of size k. Therefore, we will return the empty result.
    ii) If arr[start] * k > current_target or arr[n - 1] * k < current_target: It means that it is not possible to have a set of size k that sums up to the current_target (since the input array is sorted). Therefore, we will return the empty result in this case as well.
    iii) If k equals 2: In this case, we will follow a similar two-pointer-based approach that we followed in the previous 4 Sum solution. For this, we will call a separate function called two_sum which will take the array arr, index start, and the current_target as its input parameters and will return all the distinct pairs in arr[start ... n - 1], which sum up to the current_target.
  3. If all of the above base conditions fail, we will continue with the current function call. The approach for the same is described in the points below.
  4. Iterate i through the array arr starting from the index start and do the following:
    i) If the current element is the same as the one before it, we will skip it. This is to avoid duplicate sets, as seen in the previous 4 Sum solutions.
    ii) Recursively call k_sum with: current_target = current_target - arr[i], start = i + 1 and k = k - 1. This will bring us all of the unique sets of size k - 1 in arr[i + 1 ... n - 1] with sum equal to (current_target - arr[i]). Let us store this in sub_result.
    iii) Next, we will iterate through all of the arrays present in the sub_result and will append arr[i] at the end of each one of them.
    iv) Finally, all of the arrays present in the sub_result now have the sum equal to the current_target and have a size equal to k. Therefore, we will push all of these arrays in our final resultant array called result.
  5. The termination of the above loops means that we have considered the possibility of each element present in the array being the first element of the set of size k. Therefore, we will finally return the result.

Time Complexity

O(n^k - 1) = O(n^3)

We have k - 2 nested loops, and finally, two_sum will take O(n) time.

Since the output array will have a size equal to O(n^k) = O(n^4), printing it will take O(n^4) amount of time. However, the time taken by the four_sum function will be O(n^3).

Auxiliary Space Used

O(n^k - 1) = O(n^3)

Recursive stack size in the worst-case: O(k) = O(4) = O(1).

Size of the sub_result for the function call with k = 4: O(n^3).

Space Complexity

O(n^4)

Space used for input: O(n).

Auxiliary space used: O(n^3).

Space used for output: O(n^4) (In the worst case, there can be O(n^4) number of output quadruples each of size 4).

So, the total space complexity is: O(n^4).

Code for 4 Sum Solution 3: Two-Pointer Generic K Sum



/*

Asymptotic complexity in terms of the length of input list `n`:

* Time: O(n^3).

* Auxiliary space: O(n^3).

* Total space: O(n^4).

*/

// This function will return all the distinct pairs in arr[start ... arr.size() - 1]

// with sum of the values equal to the current_target.

vector> two_sum(vector & arr, int current_target, int start) {

   vector> result;

   int low = start, high = arr.size() - 1;

   while (low < high) {

       if (arr[low] + arr[high] == current_target) {

           result.push_back({ arr[low], arr[high] });

           low++;


           high--;


       }


       else if (arr[low] + arr[high] < current_target) {


           low++;


       }


       else {


           high--;


       }

       if (low > start) {


           while (low <= high and arr[low] == arr[low - 1]) {


               low++;


           }

       }

       if (high < arr.size() - 1) {


           while (low <= high and arr[high] == arr[high + 1]) {


               high--;


           }


       }


   }

   return result;

}

// This function will return all the distinct sets of size `k` in `arr[start ... arr.size() - 1]`

// with sum of the values equal to the `current_target`.

vector> k_sum(vector & arr, int current_target, int start, int k) {


   if (start + k > arr.size() or arr[start] * k > current_target or arr.back() * k < current_target) {


       return {};


   }


   if (k == 2) {


       return two_sum(arr, current_target, start);

   }

   vector> result;


   for (int i = start; i < arr.size(); i++) {


       if (i == start or arr[i] != arr[i - 1]) {


           // sub_result contains all the distinct (k - 1)-sized sets of


           // arr[i + 1 ... arr.size() - 1] with sum of values equal to the current_target - arr[i].


           auto sub_result = k_sum(arr, current_target - arr[i], i + 1, k - 1);

           for (auto & current: sub_result) {


               // Appending arr[i] to each of the array present in the sub_result and finally appending.


               current.push_back(arr[i]);

               result.push_back(current);


           }


       }


   }

   return result;

}

vector> four_sum(vector &arr, int target) {

   sort(arr.begin(), arr.end());


   return k_sum(arr, target, 0, 4);

}

Find out various solutions when Subarray Sum Equals K.

4 Sum Solution 4: Hash-based Pair Sum

This is not the most optimized 4 Sum solution, but it will be a good lesson for you.

In this 4 Sum solution, we will maintain a hashmap in which the key will be an integer, and the corresponding value will be an array of pairs of integers.

In this hashmap, the array corresponding to any 'key' will store all the unique pairs of indices with a sum of the values equal to 'key.'

In this 4 Sum solution, we will iterate through the array using two nested loops which will be responsible for fixing two elements of any quadruple.

Next, we will search the hashmap for all of the pairs of indices that have the sum of their values equal to (target - (sum of the two fixed elements)). While doing this, we need to be careful that any index cannot be used more than once in a quadruple. Therefore, we will need to make sure that the two fixed indices and the pair of indices that we got from the hashmap are all pairwise-distinct.

One way is to first build the required hashmap by iterating through two nested loops on the array and then following the above process. But note that this will make some unnecessary insertions in the resultant set. For example, if we have a + b + c + d = target, then this approach will iterate through the array corresponding to the key (target - a - b) once it encounters a and b in the array. Similarly, it will then iterate through the array corresponding to the key (target - c - d) once it encounters c and d in the array.

To improve upon this, we will be doing both of the following tasks simultaneously:

  • Generating the pairs for the hashmap.
  • Computing the result by iterating through the hashmap for any pair encountered in the array.

While pointing at any pair (a, b) in the array, we will only look at the pairs having a sum equal to (target - a - b) that have been previously visited in the array during the current nested traversal.

Learn what is Combination Sum and how to generate all combinations with sum equal to target problem.

Overall, our approach will be:

  1. Create a set of quadruples called result_set. This will help us avoid duplicate quadruples.
  2. Create an unordered_map called pair_sums in which the key is an integer, and the corresponding value is an array of pairs of integers. The purpose of having this hashmap has been explained above.
  3. Then, we will run two nested loops which will fix two values of a quadruple. Let us denote the two indices as i and j, respectively.
  4. Now, we need all the pairs of indices that have been encountered before the current iteration and have the sum of values equal to (target - arr[i] - arr[j]). All of these pairs exist corresponding to the key (target - arr[i] - arr[j]) in pair_sums. Therefore, we will iterate through the array corresponding to this key.
  5. While iterating through pair_sums[target - arr[i] - arr[j]], say we get a pair of indices k and l such that arr[k] + arr[l] equals target - arr[i] - arr[j].
    Now, we will have to check whether all of the indices i, j, k, and l are pairwise distinct. If they are, it means that we have now found a valid quadruple with a sum of values equal to target. Therefore, we will create a quadruple [arr[i], arr[j], arr[k], arr[l]], sort it and insert it into the result_set.
    Note that sorting the quadruple is necessary because otherwise, two same quadruples might get inserted in the result_set in different orders.
  6. Finally after iterating through the pair_sums[target - arr[i] - arr[j]], we will insert the current pair of indices {i, j} inside the array pair_sums[arr[i] + arr[j]].
  7. After the termination of the complete process, we will iterate through the result_set and insert all of the distinct quadruples in an array of quadruples called result and return the result.

Time Complexity

O(n^4 * log(n)): Time taken by the two outer nested loops: O(n^2).

Time taken for iterating through pair_sums[target - arr[i] - arr[j]] for each iteration of the two outer nested loops: O(n).

Inserting a quadruple in result_set: O(log(n^4)) = O(log(n)). (As the size of the result_set can be as large as O(n^4).

Combing all of the above, the time complexity so far is: O(n^2 * n * log(n)) = O(n^3 * log(n)).

Finally, iterating through the result_set and inserting all of the quadruples in the array called result: O(n^4 * log(n^4)) = O(n^4 * log(n)).

Auxiliary Space Used

O(n^4): For storing O(n^4) number of quadruples in the result_set.

Space Complexity

O(n^4).

Space used for input: O(n).

Auxiliary space used: O(n^4).

Space used for output: O(n^4) (In the worst case, there can be O(n^4) number of output quadruples each of size 4).

So, the total space complexity is O(n^4).

Code for 4 Sum Solution 4: Hash-based Pair Sum



/*

Asymptotic complexity in terms of the length of input list `n`:


* Time: O(n^4 * log(n)).


* Auxiliary space: O(n^4).


* Total space: O(n^4).

*/

vector> four_sum(vector &arr, int target) {

   vector > result;

   set> result_set;

   vector current(4);

   // The vector corresponding to any `key` will store the pair of indices with

   // sum of values equal to `key`.

   unordered_map < int, vector < pair < int, int > > > pair_sums;

   for (int i = 0; i < arr.size(); i++) {


       for (int j = i + 1; j < arr.size(); j++) {

           // Checking all of the pairs with sum = target - (arr[i] + arr[j]) that have been seen before.

           for (auto pair: pair_sums[target - (arr[i] + arr[j])]) {

               // The same index cannot be used multiple times in a single quadruple.

               if (i != pair.first and i != pair.second and j != pair.first and j != pair.second) {

                   current[0] = arr[i];

                   current[1] = arr[j];

                   current[2] = arr[pair.first];

                   current[3] = arr[pair.second];

                   // Sorting the array `current` before inserting it into the `result_set`


                   // so that the same quadruple do not get inserted multiple times in different orders.

                   sort(current.begin(), current.end());

                   result_set.insert(current);

               }

           }

           pair_sums[arr[i] + arr[j]].push_back({ i, j });

       }

   }

   for (auto quadruple: result_set) {

       result.push_back(quadruple);

   }

   return result;

}

We hope that these solutions to the 4 Sum problems will help you level up your coding skills. Many applications use hashing, including password security and verification, data structures and programming language compilers, tokenization, machine learning, and blockchain. 

Because of the popularity and widespread use of hashing, companies such as Amazon, Google, and Microsoft include 4 Sum interview questions and other hashing problems in their tech interviews. 

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare. 

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, FAANG+ instructors, and career coaching to help you nail your next tech interview. 

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

To learn more, register for the FREE webinar.

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Recommended Posts

All Posts