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!

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
• -10⁵ <= any element of the input list <= 10⁵
• -4 * 10⁵ <= target value <= 4 * 10⁵

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.

4 Sum Solution 1: Brute Force

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.

Time Complexity

O(n⁴).

We will run 4 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⁴).

Space used for input: O(n).
Auxiliary space used: O(1).
Space used for output: O(n⁴) (In the worst case, there can be O(n⁴) number of output quadruples each of size 4).
So, total space complexity is: O(n⁴).

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<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;
}

4 Sum Solution 2: Two Pointer

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

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²) amount of time. In this solution, we will replace those two inner loops with the two-pointer-based approach discussed above.

Time Complexity

O(n³).

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² * n).
Since the output array will have size equal to O(n⁴), printing or generating it will take O(n⁴) amount of time. Apart from that, the time taken by the four_sum function will be O(n³).

Auxiliary Space Used

O(1).

We used only a constant amount of extra space.

Space Complexity

O(n⁴).

Space used for input: O(n).
Auxiliary space used: O(1).
Space used for output: O(n⁴) (In the worst case, there can be O(n⁴) number of output quadruples each of size 4).
So, total space complexity is: O(n⁴).

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<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;
}

4 Sum Solution 3: Two Pointer Generic K Sum

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

Time Complexity

O(n^{k - 1}) = O(n³).

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⁴), printing it will take O(n⁴) amount of time. However, the time taken by the four_sum function will be O(n³).

Auxiliary Space Used

O(n^{k - 1}) = O(n³).

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

Space Complexity

O(n⁴)

Space used for input: O(n).
Auxiliary space used: O(n³).
Space used for output: O(n⁴) (In the worst case, there can be O(n⁴) number of output quadruples each of size 4).
So, total space complexity is: O(n⁴).

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

4 Sum Solution 4: Hash Based Pair Sum

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.

Time Complexity

O(n⁴ * log(n)).

Time taken by the two outer nested loops: O(n²).
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⁴)) = O(log(n)). (As the size of the result_set can be as large as O(n⁴).
Combing all of the above, the time complexity so far is: O(n² * n * log(n)) = O(n³ * log(n)).
Finally, iterating through the result_set and inserting all of the quadruples in the array called result: O(n⁴ * log(n⁴)) = O(n⁴ * log(n)).

Auxiliary Space Used

O(n⁴).

For storing O(n⁴) number of quadruples in the result_set.

Space Complexity

O(n⁴).

Space used for input: O(n).
Auxiliary space used: O(n⁴).
Space used for output: O(n⁴) (In the worst case, there can be O(n⁴) number of output quadruples each of size 4).
So, total space complexity is: O(n⁴).

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