Starting a new series on going through Blind 75. I plan to do other leetcode/codeforces questions as time goes on. If its Blind 75, It'll be tagged as such.

Problem

Given a list of numbers and a target number, find the indices of the two numbers that add up to that target.

First thoughts

My first thoughts were that the problem requires a hash map. A two pointer approach wouldn't work well without sorting, and sorting would lose the original indices. So a hash map was in order.

My thinking was that for each number in the array, I could calculate the "complement" needed (target - current_num), then use the dictionary to figure things out. Here was my first attempt trying to put my thoughts into code:

python

What a mess. Testing this out with twoSum([3, 2, 4], 6) failed. Heres why.

Bad logic

The most important thing was that my order of operations was backwards. My code calculated the complement as expected, but then it added the complement and its index to the dictionary first, and then checked if the current number was there.

Heres why thats wrong:

The complement is 6 - 3 = 3

My code immediately adds {3:0} to the dictionary

Then it checks if 3 is in the dictionary.

...well of course it is. I just put it in there. This meant my code would always match a number with itself. Look I believe in self love but we're looking for a second half. I was adding to memory before checking it.

The second issue was using the arr.index(num) method. So this works well if all the numbers are unique, but if we had [3, 3] for example with a target of 6, it would always return 0. .index() returns the first match it finds, so the second 3 is inaccessible.

So I needed to get the current number and its index at the same time, and I had to fix the order of operations.

Solution

I forgot enumerate() existed. So I used that to get both the index and the number in the loop.

And second, I swapped the order of operations and moved the return value into the if statement to terminate early.

The formalised method is :

First, calculate the complement. Then, for each number, check the memory to see if the complement I need has been seen in the past. If it has, return the pair and terminate the loop. If not, add the current number to memory so we can find it later

Putting it all together:

python

So, with our earlier example:

It sees 3, needs 3. 3 is not in memory, so it adds {3: 0}.

It sees 2, needs 4. 4 is not in memory, so it adds {2: 1}.

It sees 4, needs 2. 2 is in memory! It returns the index of 2 (which is 1) and the current index (2). Result: [1, 2].

Time and space

Time complexity: O(n)

This is because we iterate through the input array a single time. Each lookup and insertion in a hashmap takes constant time. But worse case scenario we do these operations for n items in our array.

Space complexity: O(n)

This is because of our seen dictionary. Worst case, we might have to store every number from the input array before we find our pair. This means the amount of memory grows with the size of the array, which is linear.

For the future:

The order of operations matters. Check, then update

enumerate exists. Great especially if working with duplicates.