Hashing Pattern for Problem Solving

Hashing as a Pattern

The Hashing section explains how hash maps and sets work. This page is about when to reach for one while solving a problem.

The core move is always the same: trade memory for time by remembering what you have already seen, so that a question like "has a matching element appeared before?" costs O(1) instead of a full rescan.

WITHOUT a hash structure:            WITH one:
  for each element:                    for each element:
      scan everything else               ask the map / set   ← O(1) average
  → O(n²)                              → O(n)

The Five Recurring Shapes

1. COMPLEMENT LOOKUP      "is the partner I need already here?"
   key: value  → position         e.g. two values summing to a target

2. SIGNATURE GROUPING     "which items are equivalent?"
   key: canonical form → list     e.g. words with the same letters

3. FREQUENCY COUNT        "how many of each?"
   key: item → count              e.g. first character seen exactly once

4. MEMBERSHIP SET         "does this value exist at all?"
   set of values                  e.g. longest run of consecutive integers

5. LAST-SEEN INDEX        "where did I see this most recently?"
   key: value → latest position   e.g. a repeat within distance k

Shape 1: Complement Lookup

Receipt item prices (unsorted): [12, 7, 30, 5, 18, 9]
Which two items cost exactly 25?

i=0  12 → need 13 → not seen → store {12:0}
i=1   7 → need 18 → not seen → store {7:1}
i=2  30 → need -5 → not seen → store {30:2}
i=3   5 → need 20 → not seen → store {5:3}
i=4  18 → need  7 → seen at 1 ✓   → positions 1 and 4

Sorting + two pointers also finds the pair, but loses the original positions and costs O(n log n). The map keeps positions and runs in O(n).

Shape 2: Signature Grouping

words: stone pale notes bird leap onset plea tones

signature = letters sorted:
  stone → enost   pale → aelp   notes → enost   bird → bdir
  leap  → aelp    onset → enost plea → aelp     tones → enost

groups: {enost: stone notes onset tones}  {aelp: pale leap plea}  {bdir: bird}

Sorting each word costs O(L log L). For lowercase letters, a 26-slot count array (turned into a string or tuple) gives an O(L) signature.

Shape 3: Frequency Count

"swiss" → counts {s:3, w:1, i:1}
second pass in original order: s(3) w(1) ← first with count 1 → 'w'

Two passes: count everything, then scan in the original order. Many "compare two collections" problems are also frequency maps: two strings are rearrangements of each other ⇔ identical counts.

Shape 4: Membership Set

values: [10, 4, 21, 3, 11, 5, 2, 12, 13]   (unsorted)
longest run of consecutive integers?

set = {10, 4, 21, 3, 11, 5, 2, 12, 13}
only START a walk at v when v−1 is NOT in the set:
  10: 9 absent → walk 10,11,12,13 → length 4
   4: 3 present → skip (not a start)
  21: 20 absent → walk 21 → length 1
   2: 1 absent → walk 2,3,4,5 → length 4
  ...
best = 4 — in O(n), no sorting.

Shape 5: Last-Seen Index

events: [4, 9, 2, 7, 9, 4], "same event twice within k positions?"

i=4 value 9: last seen at 1 → distance 3
  k = 2 → too far;  k = 3 → yes
Store only the LATEST position — an older one can never be closer.

Code: All Five Shapes

Output:
items summing to 25: positions 1 and 4
items summing to 39: positions 2 and 5
items summing to 100: none
group: stone notes onset tones
group: pale leap plea
group: bird
first unique in swiss: w
first unique in level: v
first unique in aabb: -
longest streak in [10, 4, 21, 3, 11, 5, 2, 12, 13]: 4
repeat within 2 in [4, 9, 2, 7, 9, 4]: false
repeat within 3 in [4, 9, 2, 7, 9, 4]: true

Choosing the Right Key

The real skill in hashing problems is designing the key. Ask: what do two items have in common when they should be treated as the same?

Complexity and Trade-offs

TIME:   O(1) average per insert / lookup → most patterns are O(n)
        Worst case O(n) per operation under heavy collisions.

SPACE:  O(n) for the stored keys — the price of the speed-up.

ALTERNATIVES when memory is tight:
  - sort + two pointers             O(n log n) time, O(1) extra
  - a fixed-size array as a "map"   when keys are small integers or letters
                                    (int[26] for lowercase letters is faster
                                    than any hash map)

How to Spot It

✓ "Have I seen ... before?" / "find a duplicate" / "first unique"
✓ "Pair / complement" on UNSORTED data where positions matter
✓ "Group items that are equivalent"
✓ "Count occurrences" / "most frequent" / "same counts"
✓ An O(n²) brute force whose inner loop is just a search → replace with a lookup

Common Mistakes

Inserting before looking up in complement problems — a value pairs with itself.

Using a mutable or unhashable key. Python lists can't be dict keys (use tuples or strings). In Java, mutating an object after using it as a key breaks lookups.

Assuming insertion order. Java HashMap and C++ unordered_map don't preserve it. Use LinkedHashMap, a separate vector, or sort the output if the order matters.

Counting with a set. A set only knows "present or not". If multiplicity matters, use a map of counts.

Overusing maps for small fixed alphabets. int[26] is simpler and faster than a map of 26 letters.

Interview Questions

Q: Why is the consecutive-streak solution O(n) even though there is a while loop inside the for loop?

The inner walk only starts at values whose predecessor is missing — the smallest member of each streak. Each value is then visited by exactly one walk (its own streak's), so all inner iterations together total at most n.

Q: How would you group words by letters in O(total characters) instead of O(L log L) per word?

Use a 26-element count array per word as the signature (converted to a string like "1#0#2#..." or a tuple). Building it is O(L), and two words share it exactly when they have the same letter counts.

Q: When is a hash map the wrong choice?

When the keys need to be ordered (use a balanced tree map for "next larger key" queries), when memory is constrained and sorting is acceptable, or when keys are small dense integers where a plain array indexed by value is faster and simpler.

Summary

• ›Hashing trades O(n) memory for O(1) lookups, turning many O(n²) searches into O(n).
• ›Five shapes: complement, signature grouping, frequency count, membership set, last-seen index.
• ›The craft is in designing the key that captures "these should be treated as the same".
• ›Look up before inserting, keep counts when multiplicity matters, and prefer arrays for small fixed alphabets.

Next, Binary Search Pattern shows how to recognise "search on a sorted space" in problems that never mention searching — including searching over the answer itself.