When solving problems that involve finding pairs or complements in a dataset, hash maps (dictionaries in Python) are often the key to achieving optimal time complexity.
A hash map stores key-value pairs and provides O(1) average-case lookup time. This means you can check if a value exists in the map almost instantly, regardless of how many items are stored in it. This is much faster than scanning through a list, which takes O(n) time.
The classic pattern for using hash maps in complement-finding problems is:
This approach transforms what would be an O(n²) brute force solution (checking every pair) into an O(n) solution by trading space for time. You use extra memory to store the hash map, but you gain significant speed improvements.
The key insight is that instead of asking "what pairs exist?", you ask "for each element, does its complement exist?" This reframing allows you to solve the problem in a single pass through the data.
1def find_complement_pair(numbers, target_sum):
2 """Find if any two numbers in the list add up to target_sum"""
3 seen = {} # Hash map to store numbers we've encountered
4
5 for num in numbers:
6 complement = target_sum - num
7
8 if complement in seen:
9 return True # Found a pair!
10
11 seen[num] = True # Remember this number for later
12
13 return False # No pair found