Two Sum: how the hash map solution works

Problem. Given an array and a target, return the indices of the two numbers that add to the target.

#Brute force first

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

O(n²). Say this out loud, state the complexity, then improve it — the path is what is being assessed.

#The insight

For each number, you know exactly what its partner must be: target - num. The question becomes "have I seen that value already?" — and that is a hash lookup.

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

O(n) time, O(n) space. One pass.

#Why checking before inserting matters

Storing num after the check prevents an element pairing with itself. With target = 6 and nums = [3, 4], inserting first would match index 0 against itself.

#The transferable lesson

Nested loop → hash lookup is the most common optimisation in these problems. It turns O(n²) into O(n) and it applies to a whole family:

• Contains Duplicate — compare len(set(nums)) to len(nums)
• Group Anagrams — key a map by the sorted letters
• Longest Consecutive Sequence — a set makes "is n−1 present?" instant
• Intersection of Two Arrays — set intersection

Whenever you catch yourself comparing every element against every other element, ask what you could look up instead of scan.

#The sorted follow-up

If the array is sorted, two pointers solve it in O(1) extra space: start at both ends and move inward based on whether the sum is too big or too small.