Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.


1. Introduction

In this tutorial, we’ll solve the 3SUM problem.

2. Problem Statement

It comes in several variations. We’ll focus on the following one.

There’s an integer array a=[a_1, a_2, \ldots, a_n] and the number s. Does the array contain a triple of integers whose sum is \boldsymbol{s}? Each element can appear in the triple only once.

For example, if a=[1, 0, 3, 17, 7] and s=21, the solution is a_1=1, a_3=3, a_4=17 but not a_5=7, a_5=7, a_5=7. As we see, the elements don’t have to be consecutive, and the indices can’t repeat in the solution.

2.1. Importance of 3SUM

3SUM is important in the theory of complexity because many problems from computational geometry, dynamic graphs, and patter matching, are reducible from 3SUM. That means that we can solve 3SUM by solving a constant number of instances of those problems (with some overhead).

That implies that those problems are in a way easier than 3SUM since they appear as its sub-problems. As a result, those problems’ upper bounds hold for 3SUM, and the lower bounds of 3SUM hold for them (provided that the overhead is negligible compared to the problems’ orders of growth).

3. Brute-Force Algorithm

We can find the triple with three nested loops:

Rendered by QuickLaTeX.com

The idea is to iterate over a and check all possible combinations of three elements. We output the triple whose sum is s if there is one; otherwise, we return false.

This algorithm is easy to understand and always returns the correct result. However, it’s asymptotically inefficient. In the worst case, no triple sums to s, so we run through all the combinations of length 3. Since there are \binom{n}{3} of them, this approach has the O(n^3) time-complexity.

4. The \boldsymbol{O(n^2)} Solution

We can do better. The key idea is to see that a_i + a_j + a_k = s is equivalent to a_k = s - (a_i + a_j). So, we hash a and then calculate the sums of \binom{n}{2} pairs one by one. We iterate over the pairs until we hit the one whose difference from s is in the hash map.

If no pair sums to the difference of s and another element of a, we return false:

Rendered by QuickLaTeX.com

The two nested loops determine the overall complexity. In the worst case, no triple sums to zero, so the algorithm runs all the \binom{n}{2} = \frac{n(n-1)}{2} \in O(n^2) iterations.

5. Conclusion

In this article, we presented two solutions to a variation of the 3Sum problem. The brute-force algorithm is simple but cubic. We can use an asymptotically much faster O(n^2) algorithm if we hash the input array, sum pairs, and look for their negatives in the hash map.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!