Algorithm: Two Sum

Quiz

Can you make this code less buggy and simpler?

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {v: idx for idx,v in enumerate(nums)}
        for idx, a in enumerate(nums):
            rest = target - a
            if rest not in map:
                continue
            found_idx = map[rest]
            if idx == found_idx:
                continue # do not use the same value twice
            return [idx, map[rest]]

Answer

Reads the array twice

The code loops over nums twice.

Pass 1: build the hash map
map = {v: idx for idx, v in enumerate(nums)}

This scans the entire array once to create the dictionary.

Pass 2: search for the answer
for idx, a in enumerate(nums):
    rest = target - a
    ...

This scans the array again to find a matching pair. Two full passes over nums.

Time complexity is still O(n), but you traverse the array twice.

Duplicate indices are hidden

{v: idx} keeps only the last index for duplicates; it often works, but it is a little fragile and less clear.

map = {v: idx for idx,v in enumerate(nums)}

For example, if nums is [1, 2, 3, 4, 1], the map becomes:

nums = [1, 2, 3, 4, 1]
map = {1: 4, 2: 1, 3: 2, 4: 3}

No need for idx == found_idx check

The original code stores all values into the map, so it has to guard against using the same element twice. If we store only values we have already seen, the current index can never be in the map yet. We store values after we check for the complement, so we never need the duplicate check.

Final code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [i, seen[need]]
            seen[x] = i

Conclusion

Improvements:

• Check nums only once.
• No need for idx == found_idx check.
• Handles duplicates cleanly.