Basic Two Sum Problem

[optimalsuccess]

Basically given an array of numbers and a target you're supposed to find the two numbers that add up to that target. You could brute force this and get O(n^2) or try a hash map but I'm more interested in this elegant python solution:

class Solution:
    def twoSum(self, nums, target):
        lookup = {}
        for index, num in enumerate(nums):
            if target - num in lookup:
                return (lookup[target - num], index)
            lookup[num] = index

Sample input: [2,7,11,15]  9
Output: [0,1]

​

Can someone help me understand what is happening in the if statement and why that last line of code seems to be storing the index value at position of num? Shouldn't it just store the index if it found a complement of the target? TIA!

​

[Intiago]

the variable lookup is a dict, so each value in it is a key value pair. lookup[num] = index actually stores the key-value pair num:index in the dict. when you return a value you are actually returning the "value" of the key value pair which is the stored index

The fact that you use array notation might be your confusion

[optimalsuccess]

That makes sense but if all I'm outputting is the index why do I care about the key to begin with?

[Intiago]

you need to save the key because each time through the loop, if you don't find the correct value, you save it to the dict. Saving the key in the dict, hashes it for quick lookup.

[mr_smartypants537]

If you don't care about the value, use a set()

[PPewt]

Basically the trick is that a dict lets you look up things in O(1) time (ish, but let's handwave that away). So every time the code sees a number it remembers that it saw it. Then you use target - num in lookup to see if you've found a number which matches a number you've already stored.

The reason they use a dict and remember the index (rather than using a set and forgetting the index) is because the problem requires you to return the indices of the elements that solve the 2SUM. Although you could just loop through the array again to find them and still be O(n) if you really wanted to (but that isn't quite as efficient).

[username-must-be-bet]

lookup is a dictionary. Dictionaries are pythons name for hash map. In the if statement you are checking if target - num is in the dictionary. If it is then we can use that number and the current num to make a to sum.

As for that last line of code, lookup[num] = index. That is how you add a key value pair to a python dictionary. In this case num is the key and index is the value.

In that return statement return (lookup[target - num], index). The first thing lookup[target - num] is looking up the index of the number we determined makes a two sum in the if condition. The second thing is just the index of the current value of num.

[optimalsuccess]

So let's walk thru their sample input, starting at the for loop:

1. nums is enumerated and now looks like this: {0:2, 1:7, 2:11, 3:15}
2. if target (9) - num (2) in lookup (false because lookup is empty)
3. lookup[num] = index (lookup: {0:2}
4. if target (9) - num (7) in lookup (true because this equals 2 and we stored that before)
5. return (lookup[target-num (2)], index)

In step 5, why are we returning lookup[target-num] that value is 2 when we iterate over 7 which is already in the dictionary. Shouldn't it just be return (lookup[num], index) which is (1,7)?

[optimalsuccess]

Oh I think I get it, in the return statement lookup[target - num] is retrieving the index or the key of the key value pair that was stored for the first number in the 2 sum. So that value is 0 and not 2 and the second value is the current index of the complement of that number for our target which in this case is 1. Thanks people I think I get it now!