dsa / dsa-hashing
20 mins
DSA Module 6: O(1) Hash Map Pair Search
Why This Matters: Hash maps turn nested O(N²) searches into single-pass O(N) algorithms.
## O(1) Lookup Hash Map Pattern
Using a hash map to look up target complements in constant average time.
```python
def two_sum(nums: list[int], target: int) -> list[int]:
seen = {} # num -> index
for i, num in enumerate(nums):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i
return []
```
MENTAL MODEL & MEMORY LAYOUT
TWO SUM HASH MAP SEARCH: Target = 9 Num = 2 ──► Diff = 7 (Not in seen) ──► Store seen[2] = 0 Num = 7 ──► Diff = 2 (Found in seen at index 0!) ──► Return [0, 1]
COMMON PITFALLS TO AVOID
- Using the same element twice (e.g. returning index [0, 0] for target 6 when nums[0]=3).
Two Sum Hash Map Pattern
nums = [2, 7, 11, 15] target = 9 # Returns [0, 1] in O(N) time!
Stores visited numbers in hash map to instantly verify target complement.
CONCEPT MASTERY CHECKPOINT
What is the average time complexity of searching a key in a Hash Map?
NEXT RECOMMENDED LESSON
DSA Module 7: Recursion & Backtracking
Challenge: Find indices of pair adding up to target using hash map.