December 22, 2014 | code

# Three Sum

Given an array and a value, find if there is a triplet in the array whose sum is equal to the given value. If there is such a triplet present in the array, then return true. Else return false. For example, if the given array is [-12, 3, 5, -2, -10, 19, -1] and given sum is 0, then there is a triplet (-2, -1 and 3) present in array whose sum is 0.

The 3Sum Problem is a fun one. We’ll look into a few ways to solve it using Ruby. Lets start by writing a failing test.

## Brute Force Approach

One possible way to solve this is to generate every unique combination of elements and see if any of the combinations evaluate to the given sum. Ruby’s Enumerable has a #combination method that will do just that.

This gets our tests passing. It looks like nice clean Ruby. Easy to read and understand. However, it is horribly inefficent. Under 100 elements this performs well. But once we get to a 500 element array it takes 3 seconds, at a 1000 it takes 25 seconds.

If we look at the formula for figuring out the number of combinations we’ll see why that is.

Where n is the number of elements in the array and k is the size of the combination (3 in this case). Combinations do not care about order - (a, b c) is the same as (c, b, a). Replacing the variables with the our values.

This evaluates to 166,167,000. That’s a lot of combinations to check! And our array size is only a 1000 - imagine if this went up to a million elements.

## Faster Approach

There is a much faster way to solve this problem, but the solution is not immediately obvious. The first step is going to be to sort the array. Lets use this sorted example array.

There is a triplet (-10, 2, 8) which sums to 0, but how do go about selecting it? The alorgithm is as follows. We lock the first element(front) in place. Starting with the one after it (start) and the very end (back) of the array, we check to see if the sum of all 3 is greater than 0. If it is, then we decrement the position of the back element. Else, we move start forward. We repeat this until we find the desired sum, or the two ends meet. If the two ends meet, we move the front element forward one and try again. Here it is visualized.

Here it is expressed in ruby:

We get a huge increase in performance.

I believe in terms of time complexity this algorithm is O(n^2).

If you find anything wrong with my math or my solution please let me know!