Hash map lookup (pattern)

Read first

Hash map

When to use it: the brute force compares every pair (O(n²)), and the question for each item is “have I already seen a value that fits with this one?”.

The move: walk once. For each item, first ask the map about its partner, then store the item.

seen = {}                      # or set() if you only need yes/no
for i, x in enumerate(items):
    partner = ...              # what x needs (target - x, x itself, a running sum ...)
    if partner in seen:
        ...                    # found it
    seen[x] = i

Cost: O(n) time, O(n) extra space. You trade memory for speed.

Problems that use it

Puzzle	What you remember	Partner of x
Two Sum	value → index	target - x
Contains Duplicate	values (a set)	x itself
Subarray Sum Equals K	running sum → count	running - k
Valid Anagram	letter → count	(compare counts)

Traps

• Ask before you store, or an item can pair with itself.
• If the input is already sorted, two pointers may solve it in O(1) space instead.

Built on the hash map concept.