Lesson 4 / 26

Hash Map Lookups

Complement search in one pass.

Store what you need to find later

A hash map (Python dict) gives average O(1) insert and lookup. The pattern: iterate once, and for each element check whether something you saw earlier completes the answer (Two Sum checks for target - x), then record the current element. Sets answer "have I seen this?" for duplicates and membership. Note the worst case can degrade, and keys must be hashable (use tuples, not lists).

Remember what you have seen

Hash maps and prefix sums turn many quadratic array problems into single passes.

Three ideas: hash map lookups, prefix sums, canonical keys and counting. — Figure 2.1 — Hash maps, prefix sums and counting.

The Two Sum pattern

From the complexity example above.

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

Check before inserting

Looking up before storing the current element avoids pairing an element with itself.

Quick check: What is the average lookup time in a hash map?

O(n)
O(1)
O(log n)
O(n²)

Answer

O(1) — Constant on average.