DSA & Algorithms
Part 14 of 21 · DSA Interview PatternsHashing, Frequency Maps & Counting — Two Sum Family & Anagrams
Hash maps for complements, frequency, anagrams, and O(1) expected lookups.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You need a complement, a count, or a membership test
Prefer
A hash map, expected linear time
Look up the thing you still need. Store the thing you have just seen. Space is O(n).
- Two Sum checks the complement before writing the current index.
- Anagram keys are sorted characters or a 26-count.
- Prefix + hash is the subarray-sum-K partner of this page.
Alternative
Sort and scan when a hash is the natural fit
Sorting is simpler sometimes and costs an extra log. Say so if you pick it.
- Writing the index before the complement check when duplicates matter.
- Claiming worst-case O(1) lookups.
- Mutating a dict while iterating its keys.
Look up, then store
The map is the memory of the scan. The key is the complement or the signature.
- 1
Compute what you need
target - x, or the anagram signature. - 2
Hit means you are done
Return the stored index, or append to that group. - 3
Miss means store this one
The later element will be the one that finds it.
Overview
Hash maps for complements, frequency, anagrams, and O(1) expected lookups.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use hash maps/sets for O(1) expected lookups, complements, frequencies, and grouping.
Recognition cues
- Two Sum / complements
- anagrams / group anagrams
- first unique character
- subarray problems with prefix+hash
Mental model
Decisions
- 1
1. See value x
- next2. need is target minus x
- 2
2. need is target minus x
- next3. Is need already stored?
- ?
3. Is need already stored?
- yes4. Return that pair
- no5. Store x at this index
- 4
4. Return that pair
- 5
5. Store x at this index
Lesson map
Hashing, Frequency Maps & Counting — Two Sum Family & Anagrams
Hash maps for complements, frequency, anagrams, and O(1) expected lookups.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB x["1. See value x"] need["2. need is target minus x"] h["3. Is need already stored?"] ans["4. Return that pair"] x -->|1. See value x to 2. need is target minus x| need need -->|2. need is target minus x| h h -->|yes| ans
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Expected O(n) time / O(n) space for hash map scans.
- Worst-case O(n^2) with adversarial hashing - rare in interviews.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Two Sum
- Group Anagrams
- Valid Anagram
- Contains Duplicate
- Longest Consecutive Sequence
- Subarray Sum Equals K
- First Unique Character in a String
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Two Sum one pass?
Answer
Store as you go; look for complement first.
Longest consecutive?
Answer
Set membership; only start run from x-1 missing.
Anagram key?
Answer
Sorted chars or frequency signature.
Hash vs sort?
Answer
Hash expected O(n); sort O(n log n) simpler sometimes.
Index vs value map?
Answer
Map value to index when positions required.
Collision talk?
Answer
Mention expected O(1); engineered attacks exist.