The problem

Let me start with identifying the problem. You have a list of numbers and one target number. The goal is to:

1. Find two numbers in the list that add up to the target
2. Return where they live in the list

Let me break this down more. Here is the example I will use:

nums = [2, 7, 11, 15]
target = 9` 

So your brain immediately identifies 2 plus 7 is 9. Cool, those are at positions 0 and 1. But for a computer, let us see how code gets there.

First solution that came to mind

This is the solution that came to mind as soon as I finished reading the description. So take the first number. Try it with every other number. If nothing works, move on. That is the double loop solution.

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length; j++) {
            if (i != j && nums[i] + nums[j] === target) return [i, j];
        }
    }
    return []
};

What is actually happening, on the first loop:

• 2 ignores 2 because of i != j but it runs the loop though
• 2 tries with 7: This passes because 2 + 7 = 9 therefore return their indexes in a array [0, 1] in this format [i, j].
• List is then returned.

Moving to another example:

nums = [3, 7, 4, 8, 2]
target = 9

Let us run through the code flow. Starting with the first flow where i = 0:

• 3 ignores 3 because of i != j but it runs the loop though
• 3 tries with 7 → j = 1
• 3 tries with 4 → j = 2
• 3 tries with 8 → j = 3
• 3 tries with 2 → j = 4

Second cycle where i = 0:

• 7 tries with 3 → j = 0
• 7 ignores 7 because of i != j but it runs the loop though
• 7 tries with 4 → j = 2
• 7 tries with 8 → j = 3
• 7 tries with 2: This passes because 7 + 2 = 9 therefore return their indexes in a array [1, 4] in this format [i, j].

You are basically checking every possible pair until something clicks. This works but it is like checking every door in a building even though you already know what room you are looking for.

As the list grows, this becomes painful in terms of the time to execute. That is why it is slow. The time complexity is O(n²) which is not really good as the size of the list grows.

Best approach

Here is the code again so we can reference it.

function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        const needed = target - nums[i];
        if (seen.has(needed)) return [seen.get(needed)!, i];
        seen.set(nums[i], i);
    }
    return [];
};

Now let us walk through it like a story and simplify it.

Step by step walk through

Let me use the examples I used above:

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

Think of seen as a notebook where you write down numbers you already passed. First loop round:

• Current number is 2 as nums[i]
• With index being 0.

Ask yourself? What number do I need to reach 9. Hence we do the following calculation 9 - 2 = 7. Now check the notebook. Do I already have 7 written down? No

So you write down on the seen (notebook) as 2 (key) lives at index 0 (value). Notebook now looks like this:

2 → 0

Move on to the second loop round:

• Current number is 7 as nums[i]
• With index being 1

Ask the same question. What number do I need? Let us do the calculation again 9 - 7 = 2. Check the seen (notebook). Do I already have 2? Yes, and it says index 0. Boom. That means 2 + 7 = target. So we return [0, 1] .And we are done.

Notice something important. We never even looked at 11 or 15. The moment we found the answer, we stopped.

Why this approach than the other

You only ever do three things:

• Look at a number.
• Do a quick math subtraction.
• Check the Map

No nested loops. No repeated work. Every number is touched once. The time complexity for this is O(n) which is faster than O(n²).

Mini exercise for yourself

Use the hash map algorithm to write a break down of how the algorithm would execute the following using the method above:

nums = [3, 7, 4, 8, 2]
target = 9

I hope you find this useful and straight to the point.