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 `sort`

ing 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(n^{3}) 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(n^{3}), 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(n^{3})? Can we solve this using just two loops and an O(n^{2}) 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(n^{2}). 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(n^{3}) (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(n^{2}) time. I think most interviewers would accept that. But there is a solution that is properly O(n^{2}), 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(n^{2}). This algorithm therefore runs in O(nlog(n)) + O(n^{2}), and the latter term dominates, so the “official” runtime answer is O(n^{2}).

This solution does run within time limits on Leetcode. The two early `return`

s at the beginning are needed to pass a particular test case containing a very large number of only `0`

s — without them, that particular test case would time out.