The 3Sum Problem | Baeldung on Computer Science

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:

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$ :

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.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex