Sets & Maps

Sets answer “have I seen this key?” Maps answer “what information belongs to this key?” Hash-based lookup, insertion, and deletion take expected $O(1)$ time.

1. Reusable Idea: Frequency Maps

A frequency map stores value -> number of occurrences:

counts = {}
for value in values:
    counts[value] = counts.get(value, 0) + 1

Build it in $O(n)$ time and $O(U)$ space, where $U$ is the number of unique values. Use it for counting, duplicate detection, most-frequent values, anagrams, and multiset comparison.

A second pass over at most $U$ entries is still $O(n)$ overall, so prefer the clearest solution over forcing everything into one loop.

2. Related Problems

3. Reusable Idea: Leverage the Input Range

Space depends on the number of possible unique keys, not the number of insertions. If a problem counts first IPv4 octets, there are only 256 possible values, so a 256-element count array uses $O(256) = O(1)$ space.

Use a fixed array when the range is small and dense; use a map when it is large, sparse, or not numeric.

4. Common Bugs and Misconceptions

• Assuming iteration order: sort explicitly when the output requires order.
• Mutating while iterating: collect changes first, then apply them in a second pass.
• Using mutable keys: use an immutable tuple or frozenset, and never modify an object while it is a key.
• Confusing missing with zero: check membership or use a safe default.
• Losing duplicate counts: a set stores presence only; use a frequency map when multiplicity matters.
• Using hashing for nearest values: hash tables support exact lookup, not predecessor, successor, or range search. Use sorting plus binary search or a tree-based map.

5. Reusable Idea: Impose a Canonical Order

When order is irrelevant, normalize equivalent inputs before comparing or hashing them:

["b", "a", "c"] -> ("a", "b", "c")
["c", "b", "a"] -> ("a", "b", "c")

Use tuple(sorted(items)) when duplicates matter, or frozenset(items) when they do not. Sorting $k$ items costs $O(k log k)$, so include that work in the complexity.

6. Applications and Related Problems

Choose the smallest structure that answers the question:

Before coding, write one concrete entry such as IP -> set of domains or value -> original index. This prevents choosing the right outer structure but the wrong value type.

7. Key Takeaways

• Trade $O(U)$ memory for expected $O(1)$ exact lookups and fewer repeated scans.
• Reach for a frequency map when the problem says count, duplicate, most frequent, or anagram.
• Exploit a small input range with a fixed-size array.
• Normalize order-insensitive data into one immutable canonical key.
• State exactly what each key and value means, and keep keys stable.