Two Sum Problem — Conquering it gradually!

Hello, Whether you’re a beginner to competitive coding or have freshly started giving interviews, you must have heard of/tried hands on this conventional programming problem called ‘Two Sum’ which simply says:

Given an array of integers, return indices of the two numbers such that they add up to the given target.

Brute Force — First thought of your mind!

Let us take the given example as

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

The very first algorithm would be:

1. Loop through the array.
2. Pick one item, store it in a variable.
3. Loop through the entire array and check if the sum equates to target.

Converting this to a simple javascript program will give us this:

var twoSumBrute = function(nums, target) {
     for(let i=0; i<nums.length; i++) {
         for(j=i+1;j<nums.length; j++) {
             if(target - nums[i] === nums[j]) {
                 return [i,j];
             }
         }
     }
};

Now, this is the very first thing that comes to your mind with just a little strain on your brain nerves! So, this can definitely be polished and made to shine 💠. Before that, let’s analyse this solution:

This solution simply loops over the array for each element of array(making it a loop inside a loop) and breaks as soon as it finds a solution(Making it bit optimised for a brute force). For our sample input, this problem would work efficiently, and will have the solution in the second pass of the inner loop over j.

However, had the input been something like this :

Input: nums = [11,15,7,2], target = 9

which is simply the same array but shuffled a bit. It would take our solution to go through each element for each single pass(every j for every i). Hence, making the worst case (the example input right above) complexity O(n2).

Thus, this definitely calls for an alternative solution, yet this brute force gives us a very important lesson!

Try and avoid nested loops➿ as much as possible!

This solutions seems to please the memory and hence giving a good space complexity. However, not the best time complexity.

NOTE : Avoid using Array.map / Array.forEach. You might end up struggling to break out of the loop!!➿

Polished Solution — (one of) The best shot of your mind!

Wait! Before you go further reading this, have a look at this hint if you haven’t seen it somewhere already. Spend some time on it. You may not then require to read the next parts to learn rather verify your solution 🔥!

Hint: Taking up some extra space won't mind. Consider using a Map/Object and see if it can help you do wonders!

Considering we can use up some more space and making the time complexity a little better (or far better than earlier 😎). Since we are considering Javascript as our language, Let’s see how we can use a simple object for a real powerful solution.

We’re going to loop through the array and check if the object has the entry (target-current element) and if not we just make an entry of the current array element into the object and every time looping over the elements, we repeat the same procedure, the moment we find an entry, we are at the solution.

Let’s algorithimise this:

1. Create an empty object.
2. Loop over the array.
3. Check if object has the difference (target-current element), if not, then simply add current element.
4. If yes, you already have the solution!

A javascript function for the same should go something like this:

var twoSum = function(nums, target) {
    var trackOb = {};
    
    for(let i=0; i<nums.length; i++) {
        let findNum = target-nums[i];
        if(trackOb[findNum] !== undefined) {
            return [trackOb[findNum], i];
        }
        
        trackOb[nums[i]] = i;
    }
}

You must be wondering why do we store the index in the object rather simply use indexOf. Let me say this,

❎ AVOID USING indexOf !!!

Let’s consider the input to be

Input: nums = [3,3], target = 6

for this input if you use indexOf, it will always return the value as 0, hence making your solution [0,0]. However, the solution should be [0,1].

IndexOf always returns the very first index of the element, which in case of duplicated elements tend to result in bugs!

Some of the gists of this enhanced solution are:

1. This solution has the worst case ( Input: nums = [11,15,7,2], target = 9 ) complexity O(n). Since, even in the worst case, it will loop till the last element just once. No nested loops!!🙅
2. Storing the index in the object is a very important step, as explained above. We will need to store the previously visited element indices in the object since we will have the current index when the solution is found. (Try the solution without storing the index and using indexOf to actually see the confusion it can create) 🤔.
3. You can alternatively use Javascript Maps too, by utilising Map.get() and Map.set() functions.

So, what happened above is not less than a magic! Just a simple object ( yet powerful 💪) improved the time complexity to a great extent. BTW, here’s the performance of the above code.

Better than 98.40%

Kudos, if you got it at the hint itself and made it. If not, thanks for reading till here, hope it helped clear a lot of things. This simple problem taught me some crucial things, hope it did to you too !

Do hit me up in comments, if something bugs you in this post!