Go to “3sum (#15)” on Leetcode ↗

It’s not particularly hard to come up with something that works for this problem. The challenge is figuring out a solution that runs in a reasonable amount of time. The test cases on Leetcode in particular get really long, and you can hit the time limit on submissions.

Solution 1: Check All Triplets

The most intuitive way to solve this problem is to generate all possible unique triplets and select the ones that sum to zero. Generating all triplets takes a bit of thought. We’ll need to loop over pretty much all the numbers for each number in the triplet, so that’ll be three nested loops. However, since each number in a generated triplet has to uniquely exist in the original set of nums, we need to stagger the indexes that we start with.

We’ll have the outermost loop start at index 0, the middle loop start at index 1, and the innermost loop start at index 2. The innermost loop will run through to the end of nums; then the middle loop will increment and the innermost loop will start at an index that’s one beyond the middle index and again run through to the end of nums. This repeats until the middle loop has reached the penultimate number in nums and the innermost loop has reached the last number in nums. Then the outermost loop increments, and it all gets repeated.

def three_sum(nums)
  triplets = gen_triplets(nums)
  zero_triplets = triplets.select { |(x, y, z)| x + y + z == 0 }
  zero_triplets.map(&:sort).uniq
end

def gen_triplets(nums)
  triplets = []
  (0...nums.length).each do |i|
    ((i + 1)...nums.length).each do |j|
      ((j + 1)...nums.length).each do |k|
        triplets << [nums[i], nums[j], nums[k]]
      end
    end
  end
  triplets
end

In the example above, we generate all possible triplets, then select the ones that sum to zero. At the end, we make sure to only return unique triplets. For this problem, [-1, 0, 1] and [0, -1, 1] are considered duplicates, but they would not be == by default, and so wouldn’t be deduplicated by uniq. By sorting each resulting triplet, both become [-1, 0, 1], and so would be deduplicated.

We can slightly re-write this solution to avoid generating a triplet in the first place if it doesn’t sum to zero, which saves a bit of computational work.

def three_sum(nums)
  zero_triplets = []
  (0...nums.length).each do |i|
    ((i + 1)...nums.length).each do |j|
      ((j + 1)...nums.length).each do |k|
        zero_triplets << [nums[i], nums[j], nums[k]] if nums[i] + nums[j] + nums[k] == 0
      end
    end
  end
  zero_triplets.map(&:sort).uniq
end

However, in either case, the three nested loops, each over almost all of nums, makes this an O(n3) solution, which is too slow for Leetcode and will timeout.

Solution 2: Check All Triplets (Using Built-in Methods)

This solution is the same as the previous one, but it’s a one-liner that entirely uses Ruby’s built-in methods. Most people would consider this cheating (and it’s also O(n3), which probably makes it too slow), but I’m including it to show what Ruby is capable of out of the box 😄

(I didn’t come up with this one — original source here.)

def three_sum(nums)
  nums.combination(3).select { |triplet| triplet.sum.zero? }.map(&:sort).uniq
end

Solution 3: Check Pairs and Opposite

How can we do better than O(n3)? Can we solve this using just two loops and an O(n2) algorithm? To figure this out, you’ll need to “realize” some properties. One such property looks like this:

If three numbers add up to zero, then that means one of those numbers is the positive/negative opposite of the sum of the other two. In other words, if x + y + z = 0, then we can say z = –(x + y).

With this realization, we can write an algorithm that generates unique pairs of nums, sums them up, and checks if the opposite of the sum also exists in the rest of nums.

def three_sum(nums)
  zero_triplets = []
  (0...nums.length).each do |i|
    ((i + 1)...nums.length).each do |j|
      pair_sum = nums[i] + nums[j]
      nums_without_current_pair = array_after_deleting_indices(nums, [i, j])
      pair_sum_opposite = -1 * pair_sum
      zero_triplets << [nums[i], nums[j], pair_sum_opposite] if nums_without_current_pair.include?(pair_sum_opposite)
    end
  end
  zero_triplets.map(&:sort).uniq
end

def array_after_deleting_indices(original_array, indices)
  array_copy = original_array.dup
  indices.sort.reverse_each { |i| array_copy.delete_at(i) }
  array_copy
end

The runtime for this comes with some asterisks. We have our two nested loops, so this solution is “at least” O(n2). In this particular implementation, the work inside the inner loop is also linear — array_after_deleting_indices needs to basically go through all the numbers in nums, so it’s also linear, and Ruby’s default Array#include? method performs a linear search (you can see this by going to the documentation for Array#include? and clicking to show the underlying implementation). So technically this is O(n3) (and it is indeed still too slow for Leetcode). However, in the context of an interview, you can make an argument that you could transform nums into a hash-based set, where finding and deleting values takes constant time, and so this solution could run in O(n2) time. I think most interviewers would accept that. But there is a solution that is properly O(n2), no asterisks required.

Solution 4: Sort and Crawl

What can we do if we sort nums first? This might also require a “realization” to come to you, although writing out an example might make it apparent. Suppose you picked three consecutive numbers somewhere in the middle of the sorted array. If they sum up to zero, great! You’ve found one of the triplets you’ll want to return. If they sum to a number greater than zero, then you can look to the left to get a smaller sum — specifically, you can do this by just looking at the number to the left of the leftmost one you’re currently looking at. If the original sum is less than zero, you can similarly look at the number to the right of the rightmost one you’re currently looking at. In either case, recompute the sum, and repeat.

For example, suppose we had the sorted numbers [-2, 0, 1, 1, 2]. If we start by looking at the middle three numbers — 0, 1, and 1, we have a sum that’s greater than zero. Then, if we look at the number to the left of the 0, we’ll have -2, 1, and 1. Now this sums to zero, and we have a working triplet. Similarly, if we started by looking at -2, 0, and 1, that sums to less than zero. We can look to the number to the right of the 1, and, as a second step, we can then look to the number to the left of 0, until we’re looking at -2, 1, and 1.

We can turn this into an algorithm by methodically going through each number in nums. We can look at the number to its left and right, calculate the sum, and move either left or right depending on the sum, until we either get to a sum of zero, or reach the left or right edge of nums without finding a sum of zero.

def three_sum(nums)
  return [] if nums.size < 3
  return [[0, 0, 0]] if nums.uniq == [0]

  zero_triplets = []
  nums.sort!
  (1...(nums.size - 1)).each do |middle_index|
    left_index = middle_index - 1
    right_index = middle_index + 1

    while left_index >= 0 && right_index < nums.size
      if (sum = nums[left_index] + nums[middle_index] + nums[right_index]) == 0
        zero_triplets << [nums[left_index], nums[middle_index], nums[right_index]]
        left_index -= 1
      elsif sum > 0
        left_index -= 1
      else
        right_index += 1
      end
    end
  end

  zero_triplets.uniq
end

Runtime: Sorting nums can be done in O(nlog(n)) time. Then, for each iteration of the middle_index loop, left_index might go to 0 and right_index might go to nums.length - 1, which would be a single, linear run through nums. Thus, the entire loop is O(n2). This algorithm therefore runs in O(nlog(n)) + O(n2), and the latter term dominates, so the “official” runtime answer is O(n2).

This solution does run within time limits on Leetcode. The two early returns at the beginning are needed to pass a particular test case containing a very large number of only 0s — without them, that particular test case would time out.