Solving the twoSums Algorithm
This algorithm is one of the most common easier algorithms that you may be asked at an interview for a entry-level software-engineer.
Now, i believe that most people can be taught almost any concept, the problem is that our brain absorbs and analyzes information differently.
Hence, as a visual learner and also as someone who needs to break the problem into small details, i will try to explain in the most simple and straight forward way this algorithm.
First, let’s present the problem:
Input: array = [3, 5, 7, 9, 12], target = 16
Output: [2, 4],
Because: array[2] (‘will give 7’) + array[3](‘will give 9’) = 16.
Intuitively, we can see what we need to get here, however i got the ideal code to be a bit confusing, hence i am going to present the ideal code and also several possible scripts that ‘cost’ more space.
Lets start:
First thing first i always write a function and express what i want as input and output.
so…..
Looking at this algorithm i know i will need some kind of iterator to solve it.
The idea is to create a JS object with a key value pair, check whether the value of two combined keys is equal to the target value that we are looking for, and if it is , return the keys stored in an array.
Let’s write a for loop, and analyze it to details:
This simple table is explanation how the for loop works here.
The for loop takes optional ( but in most cases all 3 arguments).
The (i) is initialized to 0, and that’s it, then the condition is evaluated , if it’s a true it increments the value of (i) and then runs the loop.
In this case i wanted to print into the console the elements and adding one on each loop.
Here’s the result:
Now, i want to store key:value pairs of the elements inside my comp variable that will hold a JS object
What’s that ?
well, we’re assigning the complement number and assigning the index of the original array to a value.
Still feels so abstract…. let’s actually do it.
3 is the first element, hence it’s location will be 0,
comp [target(16) — nums [i](3)] = i (0).
So, there will be a key value pair object created with the key of 13 and value of 0.
Let’s do another one, let’s say we are in our third iteration ( i is 2),
comp[target(16) — nums[i](7)] = i (2)
key value pair will be: {9:2}.
After looping through the array here is a great way to look at it ( the commented out text):
If you look at line 12 , the fourth iteration starts when the comp variable contains: {9:2. 11:1, 13:0}.
The iteration starts and now comp[nums[i]] is equal to 9, there is a key of 9 in the comp hash and therefore the return value will be the value of the key which is 2 and the index of the iteration which is 3.
Result: [2,3].