O(1) Average Lookup with dict

Average O(1) lookup is why we reach for dict/set: membership and retrieval dominate many interview solutions—prove you cannot beat sorting-only when you need order.

Why this shows up in the real world

Indexes (inverted) map term→postings list; symbol tables in compilers map name→type info.

Core idea (explained for students)

key in d, d[key], d.get(key, default). For two-sum: store complement in map while scanning.

Try this in Python

def two_sum(nums: list[int], t: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        if t - x in seen:
            return seen[t - x], i
        seen[x] = i
    return None


print(two_sum([2, 7, 11, 15], 9))

Common mistakes

• Using list for lookups → O(n).
• KeyError when assuming presence—guard or default.

Key takeaways

• set for existence, dict when you need payload per key.
• Consider frozenset keys for grouped states.