Two Sum with Hashes

Let’s say you’re given an array of integers and you want to find two numbers in that array that add up to a target number. How would you approach this problem?

Well, we can loop through each element of the array and see if its difference (target - element) exists somewhere in the loop. That sounds like a good idea. Let’s implement this:

def twosum(num_arr, target)
  num_arr.each do |n|
    if num_arr.include? target - n
      return [n, target - n]
    end
  end
  []
end

If we run it on the terminal, we get this:

The code seems to work — even with negative numbers. Great! Now, let’s take a closer look at this. Whenever we use #include?, we’re actually looping — through the num_arr. This adds another layer of loops while we’re already iterating through each element in num_arr. It’s kind of like this:

def twosum(num_arr, target)
  num_arr.each do |n|
  
    num_arr.each do |n2|
      if target - n == n2
        return [n, n2] 
      end
    end
  end
  []
end

This doesn’t give a clean/efficient feeling, does it? So how can we make this more efficient? In our case, the problem isn’t so much our approach, but rather the tool we used to implement this solution. In other words, there’s a better tool for the job.

Arrays are kind of like Hashes in a way that you can get an element of an array (value) when you give it the index (key).

Both arrays and hashes also have a similar syntax in terms of retrieving information. With arrays, each element can be retrieved easily because each element has a number associated with it. The first number starting at 0.

— image source

But how does a hash know where to find that value efficiently?

The answer is … Math.

The hash takes the key and does a math function on it. The result of that function will lead to where in memory the value is stored.

— image source

So in the image above, hash takes the key, “alice”, and runs it through a function, f(x). The result is 0, which is where “alice”’s value is.

For simplicity’s sake, let’s say f(x) = x % 10. So each time you give a hash a key, you run a modulo operation on it with 10. With the “alice” example, let’s try this out. First, keep in mind that when you crea

“alice” % 10 = 0

And the result will be 0.

The 0 will indicate where in the hash alice’s value is and return it.

Note that the 10 is a random number i used for clarity. For most hashes, the f(x) gets much more complex, like using mods with prime numbers and having the value contain an array.

Now knowing in brief detail how hashes work, let’s go back to solving Two Sum. In a very broad sense, we’re converting array, num_arr, into a hash because retrieving our target value is faster this way.

def twosum(num_arr, target)
  hash = {}

  num_arr.each do |n|

    if !hash[target - n].nil?
      return [n, target - n]
    end

    hash[n] = target - n

  end

  []
end

So we iterate through the num_arr and check if that hash already has the difference in there. If so, you can return the two numbers, otherwise, store the difference in the hash and move on.

num_arr = [1,2,3]
target = 4
hash = {}

First Iteration: n = 1
target - n = 3
Does 3 exist in hash?
hash << 1       # more accurately, hash[1] = 3
hash = { 1 => 3 }
Second Iteration: n = 2
target - n = 2
Does 2 exist in hash?
hash << 2       # more accurately, hash[2] = 2
hash = { 1 => 3, 2 => 2 }
Third Iteration: n = 3
target - n = 1
Does 1 exist in hash?
hash = { 1 => 3, 2 => 2 }

The main takeaway from this is that there’s no way to find a specific value from an array without looking through the entire array. But with hashes, values can be found much more efficiently by turning the values into a key instead.

—

Bonus: Here’s the final solution refactored:

def twosum(num_arr, target)
  hash = {}
  num_arr.each do |n|
    return [n, target - n] unless hash[target - n].nil?
    hash[n] = target - n
  end
  []
end