Two Sum Problem in Ruby
At this point, most software engineers probably already heard or seen the “Two Sum” problem before. It is one of the most popular and highest frequency problems that appear in real interviews’ questions. Usually, companies will throw this kind of an accessible first-round phone screen interview. Not only you need to solve it under the time limit they provided, but also expecting the best solution of your code efficiency(big o notation). If you never hear or see the “Two Sum” problem before, dont worry, I will explain everything in this article.
So, here is the “Two Sum” question:
Before trying to solve the problem, we need to understand the problem and what the issue is asking. We can break down the problem into a couple of steps; perhaps we can find some patterns to solve the problem. Suppose, given the array of variables called nums= [2,7,11,15], and the target value is equal to 9. We want to find two numbers inside the nums array that add up to the target (9 in this case). If we look at the nums array again, there are only two numbers add up equal to 9, which is the indices of 0 and 1 (2+7). Notice the question is asking to return the index, not the value(number) of that index.
After understanding the problem, we can begin to code and solve the problem. There is a different kind of ways of solving the problem. Most people that never or not familiar with solving algorithms and data structures before usually start with the brutal force approach, which also the easiest way to solve the problem.
Here, we are looping the indices in an array from zero to the nums length minus one(0…nums.length-1), since index starts with 0, we dont want to out of bound. The second loop is where we put the pointer for the next index and loop through the entire array beside the first index. If nums of i + nums of j are equal to target, then we want to return the index. Although it gives us the correct solution, it is still an inefficient way of solving the problem. The time complexity of this algorithm is at O(n²). It is too slow, and it will out of control when the array is getting larger. There is a better way of solving it with a linear time complexity O(n).
The hashing approach is much more efficient and scalable. First, we create a new hash called checked, and we iterate with each_with_index method. Since we know the target value; therefore; we only need to know the value of the target minus each number of the index that exists in the array. For instance, we have nums= [2,7,11,15] with a target of 9. Let say we are starting at 2; the number that we must add equally to 9 is 9–2=7; the answer is 7. According to this information, we only need to scan the number 7 in the nums array, and if number 7 exists in the array, we know how to solve the problem. If not, we need to move on to the next number until we find the number 7. From the picture above we store diff= target (9) — value([2,7,11,15]) and use hash check[diff] to see if it exists or not. The first value is 7( 9–2 =7), checked[7] doesn’t exist so we store the checked[value]=i (checked[2]=0). Here, the hash table “checked” has a key of 2 and a value of 0 ({2=>0}). The next iteration value is 7; in this case, the diff is equal to 2 (9–7). Once again, we check if it exists in our checked table or not. From the first iteration, we can see it exists(checked[2]=0). If exist we return (checked[2],i), i is 1 (we starts 0,1,2… in array index, so 1is the second iteration. So there you go final solution return [0,1].
The hash data structure is the best option to solve this kind of problem; it maintains unique elements consistently. Since the loop is not nested and having a hash table run in a constant complexity for element lookup, now we solve the problem from O(n²) to a linear O(n) time complexity(from 3488 ms to 32 ms).
Overall, there is no particular one right answer for this solution, as long as you give the right outcome and optimize your code efficiency, you are good-to-go. One of the difficulties about solving algorithm and data structure is not about getting the right solution, but how are we getting the best solution with our code efficiency. The time complexity of your code solving that solution is what companies are looking for in interviews. Therefore, when you think you finished solving algorithm and data structure problems, think twice before you submit your final answer.