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 and the number . Does the array contain a triple of integers whose sum is ? Each element can appear in the triple only once.
For example, if and , the solution is but not . 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 and check all possible combinations of three elements. We output the triple whose sum is if there is one; otherwise, we return .
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 , so we run through all the combinations of length 3. Since there are of them, this approach has the time-complexity.
4. The Solution
We can do better. The key idea is to see that is equivalent to . So, we hash and then calculate the sums of pairs one by one. We iterate over the pairs until we hit the one whose difference from is in the hash map.
If no pair sums to the difference of and another element of , we return :
The two nested loops determine the overall complexity. In the worst case, no triple sums to zero, so the algorithm runs all the iterations.
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 algorithm if we hash the input array, sum pairs, and look for their negatives in the hash map.