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:

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:

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:

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!