Two Sum Problem Classic Hash Solution in DSA Python

Mental Model

We find two numbers that add up to a target by remembering numbers we've seen before and checking if the partner number is already known.

Analogy: Imagine you want to buy two items that together cost exactly your budget. You keep a list of prices you've seen and check if the price needed to reach your budget is already on your list.

nums: [2, 7, 11, 15]
hash_map: {}

We scan nums left to right, adding each number to hash_map with its index.
For each number, we check if target - number is in hash_map.

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find indices of two numbers that add up to 9

Step 1: Check first number 2, look for 9 - 2 = 7 in hash_map

nums: [2, 7, 11, 15]
hash_map: {}
No 7 found, add 2 with index 0
hash_map: {2:0}

Why: We need to remember 2 to find its partner later

Step 2: Check second number 7, look for 9 - 7 = 2 in hash_map

nums: [2, 7, 11, 15]
hash_map: {2:0}
2 found at index 0, pair found (0,1)

Why: We found the partner 2 that sums with 7 to 9

Result:

Indices: [0, 1]

Annotated Code

DSA Python

from typing import List

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

# Driver code
sol = Solution()
result = sol.twoSum([2, 7, 11, 15], 9)
print(result)

for i, num in enumerate(nums):

iterate over each number with its index

complement = target - num

calculate the needed partner number to reach target

if complement in hash_map:

check if partner number was seen before

return [hash_map[complement], i]

return indices of the two numbers that sum to target

hash_map[num] = i

store current number with its index for future checks

Output

[0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time lookups in the hash map

Space: O(n) because we store up to n numbers in the hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this hash map method is much faster by trading space for speed

Edge Cases

empty list

returns None or no pair found because no numbers exist

DSA Python

for i, num in enumerate(nums):

no two numbers sum to target

function returns None implicitly as no return happens

DSA Python

if complement in hash_map:

multiple pairs possible

returns the first valid pair found

DSA Python

return [hash_map[complement], i]

When to Use This Pattern

When asked to find two elements summing to a target quickly, use a hash map to remember seen numbers and check complements in one pass.

Common Mistakes

Mistake: Checking if current number is in hash map before adding it, causing missing pairs where both numbers are the same
Fix: Check for complement in hash map before adding current number to avoid missing pairs

Summary

Find two indices of numbers that add up to a target using a hash map for fast lookup.

Use when you need to find pairs summing to a target efficiently in one pass.

Remember to check for the complement before adding the current number to the hash map.