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. Use 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.

3. 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.

4. 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.

5. 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.

Match an Earlier Complement

In Two Sum, store value -> earlier index. For each value, look up target-value before recording the current index, so one position cannot match itself. [3,3] with target 6 must still work: the second occurrence finds the first. Expected time is $O(n)$ and space $O(n)$.

Hash operations are expected constant-time only for bounded-size keys and ordinary collision behavior. Building or hashing a length-k string or tuple can cost $O(k)$; include that cost when canonicalizing groups. A hash match alone is not proof of equality if you store only a lossy fingerprint instead of the full key.

6. 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.

Continue to Sliding Windows for counts that change as a range moves, and Prefix Sums for maps from running totals to counts or indices.