Conquering the Notorious Two Sum Problem in Ruby

A few weeks ago I had my first ever technical interview and let’s just say it could’ve gone much better (begins sobbing). Thankfully it was just a mock interview that was simply for practice, but the interviewer asked me just one question. This question is a fairly common technical interview question and although I struggled to solve it during the interview, but I’m happy to say that I’ve got it figured out!

Sow what’s the question?

Okay. So the question is telling us to return the indices of two number that add up to the target value. Before we can approach the question we have to make sure we understand what it’s asking. Let’s say for example that we have an array nums = [1, 4, 7, 10, 13] and the target value is 14. We want to find two number in this array that add up to 14. If we check the nums array, we have two different options: 4 + 10 and 1 +13. The indices would be 1 and 3, and for the second set the indices are 0 and 4. Remember we have to index and not the number!

def two_sum(nums, target)
    checked = {}
    
    nums.each_with_index do |value, i|
        diff = target - value
        
        if checked[diff]
            return [checked[diff], i]
        else
            checked[value] = i
        end
    end
end

The best and most efficient way to solve the problem is with a hash. First, we start by creating a new hash and will call that hash checked. Then, we’ll iterate over it with the each_with_index method. We already know the target value that we need to reach, so all we need to know is the value of target minus each number in the array. For example, we need to get to 14, and the first number in the nums array is 1, so we must add 13 to get to 14. So, based off of this information we need to check our hash for the number 13. If we find it, we’ll return the indices of those two values. If we don’t find the value we need, we’ll move onto the next number. In our code, we write diff = target — value to ensure we find the correct number that will reach our target value.

There are other ways to solve this problem but it would require a nested iteration which would not be the most efficient. A hash allows us to run in a more linear time complexity. Happy Coding!