Hash Map & Set Basics: Count, Look Up, Group

Most array problems get easier the moment you can answer "have I seen this before?" in $O(1)$ . A Python set or dict gives you exactly that. This note covers the five everyday moves: remember what you've seen, look up a complement, count, group by a key, and check a composite key. Almost every other hashing pattern on this site is one of these with a twist.

The idea#

A nested loop compares every pair, which is $O(n^2)$ . A hash table lets you swap that inner loop for a lookup. As you walk the input once, you store a small fact about each item, and each new item asks the table one question.

The work is in choosing what to store and what to ask:

Move	Store	Ask
Seen-set	each value	"Is `x` already in the set?"
Complement	`value -> index`	"Is `target - x` in the map?"
Count	`value -> count` (`Counter`)	"Do two counts match?"
Group	`key -> list of items`	"Which bucket does this key go in?"
Composite key	tuples like `(row, digit)`	"Has this combination appeared?"

Two details decide whether a solution is right. For grouping, the key must be canonical: two items that belong together must produce exactly the same key, for example "".join(sorted(word)) or a tuple of 26 letter counts. For complements, check before you store, so an item never pairs with itself.

How to spot it#

The signals are usually in the wording of the question.

"Contains a duplicate", "appears twice", "first repeated": a seen-set.
"Two numbers that add up to", "pair with difference": complement lookup.
"Anagram", "same letters", "rearrange": frequency counts.
"Group", "bucket", "categorize the strings": a canonical key into a defaultdict(list).
"Longest consecutive run" in an unsorted array: a set, and start counting only where x - 1 is missing.
"Valid board", "no repeats in any row, column or box": composite keys.

If the brute force compares every pair and the input is not sorted, a hash table is usually the first thing to try.

Template#

Most of these problems share one loop. Pick the state, the question and the update.

table = empty set or map
for each item (with its index if needed):
    key = what identifies this item for the question
    if the question about key is answered by table:
        record or return the answer
    update table with key
return the answer

Longest consecutive run has its own shape, because you walk the set, not the input:

values = set(items)
best = 0
for each x in values:
    if x - 1 not in values:          # x starts a run
        length = 1
        while x + length in values:
            length += 1
        best = max(best, length)
return best

Each value is visited by the inner loop only once, from its run's start, so the whole thing stays $O(n)$ .

Pitfalls#

These are the mistakes that most often cost a correct answer.

Pairing an item with itself. In complement problems, look up first, then store. Storing first lets x match its own target - x.
Lists as keys. A list is not hashable. Turn it into a tuple or a string before you use it as a dict key or put it in a set.
A key that isn't canonical. sorted(word) is a list; use "".join(sorted(word)) or tuple(sorted(word)). A count key must cover all 26 letters in the same order.
Sorting when you don't need to. Sorting each word costs $O(k \log k)$ . For long words, a 26-count tuple is $O(k)$ .
Starting a run from every value. In longest consecutive, counting up from every x is $O(n^2)$ on input like 1..n. Only start where x - 1 is missing.
Delimiters that can appear in the data. When you join strings for encoding, any separator character can also appear inside a string. Prefix each string with its length instead.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Two Sum and Contains Duplicate.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Two Sum

Keep a map from value to index. For each x, check whether target - x is already in the map before you add x, so an element never pairs with itself.

Hint: Contains Duplicate

A seen-set: return as soon as an item is already in it. Comparing len(set(nums)) with len(nums) is the same idea in one line.

Hint: Valid Anagram

Two strings are anagrams exactly when their letter counts match. Check the lengths first, then compare two Counters, or one 26-slot count that you increment for one string and decrement for the other.

Hint: Group Anagrams

Give every word a canonical key that all its anagrams share, then append the word to groups[key] in a defaultdict(list). The sorted letters work as a key; a tuple of 26 counts avoids the sort.

Hint: Longest Consecutive Sequence

Put everything in a set. Only start counting from x when x - 1 is not in the set, then walk up while x + 1, x + 2, ... are present.

Hint: Encode and Decode Strings

Any separator can appear inside the strings themselves. Write each string as its length, a marker like #, then the string. When decoding, read digits up to the marker, then take exactly that many characters.

Hint: Valid Sudoku

Only filled cells matter. Track what each row, each column and each 3×3 box has seen; the box for cell (r, c) is (r // 3, c // 3). One set of composite keys like ("row", r, d) does the same job in a single structure.

Key takeaways#

A set or dict turns "have I seen this?" into an $O(1)$ question, which replaces a nested loop.
Choose what to store and what to ask: values, complements, counts, canonical keys or composite keys.
For pairs, look up before you store.
Grouping keys must be canonical and hashable: a joined string or a tuple, never a list.
For runs in an unsorted array, start only where x - 1 is missing to stay $O(n)$ .

Core idea#

A set or dict answers "have I seen this?" in $O(1)$ . That replaces the inner loop of a pairwise brute force with one lookup per item.

Key points#

Decide what to store and what to ask for each item.
Duplicates: a seen-set. Return when an item is already in it.
Pairs summing to a target: map value to index, look up target - x before storing x.
Anagrams: equal letter counts (Counter or a 26-slot array).
Grouping: a canonical key into defaultdict(list), such as sorted letters or a 26-count tuple.
Longest consecutive run: a set, and count only from values where x - 1 is missing.
Validation: composite keys, such as (r // 3, c // 3) for a 3×3 box.

Moves#

Move	Store	Ask
Seen-set	values	is `x` in the set?
Complement	value to index	is `target - x` there?
Count	value to count	do counts match?
Group	key to list	which bucket?
Composite key	tuples	seen this combination?

Template#

table = empty set or map
for each item:
    key = what identifies the item for the question
    if table answers the question about key:
        record or return the answer
    update table with key
return the answer

Pitfalls#

Storing before the lookup. An item then pairs with itself.
Lists as keys. Use a tuple or a joined string.
Non-canonical keys. Every anagram must produce the same key.
Counting a run from every value. That is $O(n^2)$ ; start only at run starts.
Separator characters in encoded strings. Use a length prefix instead.

Say it in an interview#

"I trade the inner loop for a hash lookup, so it's one $O(n)$ pass."
"The group key is canonical: all anagrams share the same sorted letters."