Hash Maps and Sets

Hash maps and hash sets are the single highest-leverage data structures in interview problem solving. Both are built on the same idea: a hash function converts a key into a bucket index, so checking "have I seen this before?" or "what value is paired with this key?" takes O(1) time on average instead of the O(n) you'd pay scanning a list. A hash set stores only keys (great for membership and de-duplication), while a hash map stores key-value pairs (great for counting, grouping, or remembering "where did I see this before?"). The core trade-off is space for time: you spend extra memory building the structure so you can avoid repeated linear scans.

Common problem shapes

Most hash-based interview problems fall into a handful of recurring patterns:

• Complement lookups. Given a target relationship between two values (like a + b = target), walk the array once, and for each element check whether the value that would complete the relationship is already in the map. This is the classic "two-sum" pattern and it turns an O(n^2) nested-loop search into a single O(n) pass.
• Frequency counting. Build a map from value to occurrence count. This powers anagram checks, majority-element problems, and — as in this subject's final problem — counting structured tuples like geometric triplets by looking up how many times a needed value has appeared before or after the current index.
• Membership / de-duplication. A set answers "is this here?" or "have I already used this row/column/box?" in O(1), which is exactly what board validation (Sudoku) and "mark these coordinates" (zero striping) problems need.
• Grouping and "seen" tracking. Map a derived key (like a sorted string, or "is this the start of a sequence?") to a value or a set of items, which is how you find groups of related items or a run's starting point in O(1) per element, enabling the longest-consecutive-run trick.

A generic template

seen = {}                      # or set()
for item in collection:
    complement = derive(item)  # e.g. target - item, or item itself
    if complement in seen:
        # found a match / relationship — record or return it
    seen[item] = extra_info     # or seen.add(item)

The shape barely changes across problems — what changes is what you store (just the key, or the key with its index/count/frequency) and what "complement" means for that problem.

Complexity

Because insertion, lookup, and deletion are O(1) on average, these patterns typically run in O(n) time and O(n) space — you visit each element a constant number of times and store at most n entries. The important caveat is "average case": a poorly distributed hash function or adversarial input can cause many keys to collide into the same bucket, degrading worst-case lookup to O(n) per operation (O(n^2) overall). In practice, language-standard hash maps/sets (Python's dict/set, Java's HashMap/ HashSet) have good general-purpose hash functions, so this is rarely a concern in interviews, but it's worth knowing why "hash map lookup is O(1)" is technically an average-case statement.

Common pitfalls

• Mutating a collection while iterating it. Adding or removing keys from a dict/set during a for loop over it can raise errors or silently skip elements — collect changes separately and apply them after the loop, or iterate over a copy.
• Hashable-key constraints. Only immutable, hashable values (numbers, strings, tuples of hashable items) can be dict keys or set elements — lists and other mutable containers cannot, which matters for problems like "record this coordinate" (use a tuple, not a list).
• Dict vs. set confusion. If you only need "have I seen this?", a set is simpler and uses less memory than a map with throwaway values; reach for a map only when you actually need to associate extra information (a count, an index, a list of positions) with each key.

What you'll practice

This subject walks through five problems that build on these ideas, from straightforward to more involved:

1. Pair Sum - Unsorted — the canonical two-sum, solved with a complement-lookup hash map.
2. Verify Sudoku Board — using hash sets to catch duplicate digits across rows, columns, and 3x3 boxes.
3. Zero Striping — recording "dirty" rows and columns with sets before mutating a matrix in place.
4. Longest Chain of Consecutive Numbers — using a hash set to find run lengths in O(n) without sorting.
5. Geometric Sequence Triplets — combining hash maps of value counts to count triplets efficiently.