Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Many FAANG companies, like Google and Amazon, use the 4 sum problem to test the coding skills of software engineering candidates. Here, we will cover four methods to solve this problem. Let's dive in!

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

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

Output:

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

- 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
- -10
^{5}<= any element of the input list <= 10^{5} - -4 * 10
^{5}<= target value <= 4 * 10^{5}

We have provided four solutions. Throughout this editorial, we will refer to the input array as `arr`

, its size as `n`

and the target sum as `target`

.

A brute force solution that most of you might come up with initially is to run 4 nested loops and check 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 note that, in the case when 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 extra space and time.

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

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

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

- The outermost loop will fix an element
`arr[i]`

so that the 3 nested inner loops could find the triplets with sum equal to`(target - arr[i])`

. - The second loop will fix an element
`arr[j]`

ahead of the index`i`

so that the 2 nested inner loops could find the pairs with 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`

.

An observation that will help us avoid duplicate quadruples: 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 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 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 for being 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.

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

O(n^{4}).

We will run 4 nested loops on the input array of size `n`

.

O(1).

We used only a constant amount of extra space.

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
int n = arr.size();
vector<vector<int>> 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;
}
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;
}
```

Given a sorted array nums of size `m`

, we can find all the unique pairs with sum equal to any number `k`

in O(m) amount of time. The approach for the same is given below:

- Initialize the iterators
`low = (starting index of nums)`

and`high = (ending index of nums)`

. - Initiate a process that runs until the condition
`low < high`

is satisfied. The approach followed by the process is:- 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`

. - 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. - 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. - Next, we need to make sure that the duplicate pairs do not get inserted to our result. To do this, we will skip the duplicate occurrences of
`arr[low]`

and`arr[high]`

(if any).

- If

In the previous solution, the inner two loops were responsible to get us all the unique pairs with sum equal to `(target - arr[k] - arr[l])`

in O(n^{2}) amount of time.
In this solution, we will replace those two inner loops with the two-pointer-based approach discussed above.

O(n^{3}).

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 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}).

O(1).

We used only a constant amount of extra space.

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
int n = arr.size();
vector<vector<int>> 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++;
}
// Skiping 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;
}
```

If you are asked the “Four Sum” problem in a technical interview, it's possible that the interviewer will ask you to extend your solution to “Five Sum,” “Six 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.
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 sum of the values equal to the given `target`

.
The approach that we will follow for the `k_sum`

function is described below:

- 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`

. - We will then check for the following base cases:
- 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. - 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. - If
`k`

equals 2: In this case, we will follow a similar two-pointer-based approach that we followed in the previous 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`

.

- If

If all of the above base conditions fail, we will continue with the current function call. The approach for the same is described below.

- Iterate
`i`

through the array`arr`

starting from the index`start`

and do the following:- If the current element is the same as the one before it, we will skip it. This is to avoid the duplicate sets as seen in the previous solutions.
- 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`

. - 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 it. - Finally, all of the arrays present in the
`sub_result`

now have the sum equal to the`current_target`

and have the size equal to`k`

. Therefore, we will push all of these arrays in our final resultant array called`result`

.

- The termination of the above loops means that we have considered the possibility of each element present in the array for being the first element of the set of size
`k`

. Therefore, we will finally return the`result`

.

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 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}).

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}).

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> two_sum(vector<int> & arr, int current_target, int start) {
vector<vector<int>> 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<vector<int>> k_sum(vector<int> & 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<vector<int>> 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<vector<int>> four_sum(vector<int> &arr, int target) {
sort(arr.begin(), arr.end());
return k_sum(arr, target, 0, 4);
}
```

This is not the most optimized solution, but it is a good-to-know method. In this 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 sum of the values equal to 'key'.

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 sum equal to `(target - a - b)`

that have been previously visited in the array during the current nested traversal.

Overall, our approach will be:

- Create a set of quadruples called
`result_set`

. This will help us avoid duplicate quadruples. - 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. - Then, we will run two nested loops that will fix two values of a quadruple. Let us denote the two indices as
`i`

and`j`

, respectively. - 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. - 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. - 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]]`

. - 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`

.

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)).

O(n^{4}).

For storing O(n^{4}) number of quadruples in the `result_set`

.

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
vector <vector<int>> result;
set<vector<int>> result_set;
vector<int> 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 problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

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, and career coaching to help you nail your next tech interview.

We offer 18 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

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

Many FAANG companies, like Google and Amazon, use the 4 sum problem to test the coding skills of software engineering candidates. Here, we will cover four methods to solve this problem. Let's dive in!

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

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

Output:

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

- 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
- -10
^{5}<= any element of the input list <= 10^{5} - -4 * 10
^{5}<= target value <= 4 * 10^{5}

We have provided four solutions. Throughout this editorial, we will refer to the input array as `arr`

, its size as `n`

and the target sum as `target`

.

A brute force solution that most of you might come up with initially is to run 4 nested loops and check 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 note that, in the case when 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 extra space and time.

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

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

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

- The outermost loop will fix an element
`arr[i]`

so that the 3 nested inner loops could find the triplets with sum equal to`(target - arr[i])`

. - The second loop will fix an element
`arr[j]`

ahead of the index`i`

so that the 2 nested inner loops could find the pairs with 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`

.

An observation that will help us avoid duplicate quadruples: 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 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 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 for being 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.

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

O(n^{4}).

We will run 4 nested loops on the input array of size `n`

.

O(1).

We used only a constant amount of extra space.

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
int n = arr.size();
vector<vector<int>> 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;
}
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;
}
```

Given a sorted array nums of size `m`

, we can find all the unique pairs with sum equal to any number `k`

in O(m) amount of time. The approach for the same is given below:

- Initialize the iterators
`low = (starting index of nums)`

and`high = (ending index of nums)`

. - Initiate a process that runs until the condition
`low < high`

is satisfied. The approach followed by the process is:- 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`

. - 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. - 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. - Next, we need to make sure that the duplicate pairs do not get inserted to our result. To do this, we will skip the duplicate occurrences of
`arr[low]`

and`arr[high]`

(if any).

- If

In the previous solution, the inner two loops were responsible to get us all the unique pairs with sum equal to `(target - arr[k] - arr[l])`

in O(n^{2}) amount of time.
In this solution, we will replace those two inner loops with the two-pointer-based approach discussed above.

O(n^{3}).

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 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}).

O(1).

We used only a constant amount of extra space.

O(n^{4}).

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
int n = arr.size();
vector<vector<int>> 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++;
}
// Skiping 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;
}
```

If you are asked the “Four Sum” problem in a technical interview, it's possible that the interviewer will ask you to extend your solution to “Five Sum,” “Six 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.
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 sum of the values equal to the given `target`

.
The approach that we will follow for the `k_sum`

function is described below:

- 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`

. - We will then check for the following base cases:
- 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. - 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. - If
`k`

equals 2: In this case, we will follow a similar two-pointer-based approach that we followed in the previous 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`

.

- If

If all of the above base conditions fail, we will continue with the current function call. The approach for the same is described below.

- Iterate
`i`

through the array`arr`

starting from the index`start`

and do the following:- If the current element is the same as the one before it, we will skip it. This is to avoid the duplicate sets as seen in the previous solutions.
- 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`

. - 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 it. - Finally, all of the arrays present in the
`sub_result`

now have the sum equal to the`current_target`

and have the size equal to`k`

. Therefore, we will push all of these arrays in our final resultant array called`result`

.

- The termination of the above loops means that we have considered the possibility of each element present in the array for being the first element of the set of size
`k`

. Therefore, we will finally return the`result`

.

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 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}).

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}).

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> two_sum(vector<int> & arr, int current_target, int start) {
vector<vector<int>> 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<vector<int>> k_sum(vector<int> & 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<vector<int>> 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<vector<int>> four_sum(vector<int> &arr, int target) {
sort(arr.begin(), arr.end());
return k_sum(arr, target, 0, 4);
}
```

This is not the most optimized solution, but it is a good-to-know method. In this 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 sum of the values equal to 'key'.

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 sum equal to `(target - a - b)`

that have been previously visited in the array during the current nested traversal.

Overall, our approach will be:

- Create a set of quadruples called
`result_set`

. This will help us avoid duplicate quadruples. - 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. - Then, we will run two nested loops that will fix two values of a quadruple. Let us denote the two indices as
`i`

and`j`

, respectively. - 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. - 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. - 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]]`

. - 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`

.

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)).

O(n^{4}).

For storing O(n^{4}) number of quadruples in the `result_set`

.

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, total space complexity is: O(n^{4}).

```
/*
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<vector<int>> four_sum(vector<int> &arr, int target) {
vector <vector<int>> result;
set<vector<int>> result_set;
vector<int> 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 problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

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, and career coaching to help you nail your next tech interview.

We offer 18 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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart

- Designed by 500 FAANG+ experts
- Live training and mock interviews
- 17000+ tech professionals trained

00

Days

:

00

Hrs

:

00

Mins

:

00

Secs