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.

class ThreeSumTest < Minitest::Test
  def test_three_sum
    elements = [-12, 3, 5, -2, -10, 19, -1]

    assert three_sum(elements, 0)
  end

  def test_three_sum_with_no_solution
    elements = [-2, -1, 2]

    assert !three_sum(elements, 0)
  end
end

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.

def three_sum(elements, sum)
  elements.combination(3).detect do |a, b, c|
    (a + b + c) == sum
  end
end

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.

10 elements:   0.000000    0.000000   0.000000 (  0.000039)
100 elements:  0.030000    0.000000   0.030000 (  0.026817)
500 elements:  3.100000    0.010000   3.110000 (  3.138343)
1000 elements: 25.030000   0.100000  25.130000 ( 25.319947)

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:

def three_sum_fast(ary, sum)
  ary.sort!

  (0..ary.length - 3).each do |i|
    front = ary[i]
    start_index = i + 1
    back_index = ary.length - 1

    while(start_index < back_index) do
      start = ary[start_index]
      back = ary[back_index]

      if (front + start + back) > 0
        back_index -= 1
      else
        start_index += 1
      end

      return true if front + start + back == sum
    end
  end

  # No matches found
  false
end

We get a huge increase in performance.

user             system     total      real
10 elements:     0.000000   0.000000   0.000000 (  0.000019)
100 elements:    0.000000   0.000000   0.000000 (  0.000520)
500 elements:    0.010000   0.000000   0.010000 (  0.010293)
1,000 elements:  0.050000   0.000000   0.050000 (  0.051667)

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!