# Hash Map Lookups — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/h-map

> 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.](assets/figures/dsa-interview-patterns/section-2-map.svg) — Figure 2.1 — Hash maps, prefix sums and counting.

## The Two Sum pattern

From the complexity example above.

```python
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.

**Quiz:** What is the average lookup time in a hash map?

- [ ] O(n)
- [x] O(1)
- [ ] O(log n)
- [ ] O(n²)

*Answer:* O(1). Constant on average.