PATTERN 2: Hashing as State Memory
D
Qubits of DPK
April 11, 2026
Core DSA
Pattern 2 is where brute force dies instantly and interviews suddenly feel fair.
Core Idea (lock this)
“Store what I’ve already seen so I don’t recompute or rescan.”
Hashing is not about HashMap syntax.
It’s about remembering state.
If your brute force checks past elements again and again → this pattern applies.
How to Recognize This Pattern (CRITICAL)
Think Hashing when:
- You need fast lookup (O(1) expected)
- You’re checking existence / frequency
- You’re detecting repeats, cycles, pairs
- You hear:
If nested loops are checking history →
If memory can replace loops →
30 MUST-DO INTERVIEW PROBLEMS
(10 Easy → 10 Medium → 10 Hard)
EASY (1–10): Lookup & Frequency Basics
Goal: make hashing feel natural, not magical.
- #Two Sum – LC 1 - COMPLETED
- #Contains Duplicate – LC 217 - COMPLETED
- #Valid Anagram – LC 242 - COMPLETED
- #First Unique Character in a String – LC 387 - COMPLETED
- #Intersection of Two Arrays – LC 349 - COMPLETED
- #Intersection of Two Arrays II – LC 350 - COMPLETED
- #Find All Numbers Disappeared in an Array (Set approach) – LC 448 - COMPLETED
- #Ransom Note – LC 383 - COMPLETED
- #Happy Number – LC 202 - COMPLETED
- #Isomorphic Strings – LC 205 - COMPLETED
After these:
You should instinctively ask, “Can I store this?”
️ MEDIUM (11–20): Hashing + Logic
English explanation first.
- #Group Anagrams – LC 49 - COMPLETED
- #Longest Consecutive Sequence – LC 128 - COMPLETED
- #Subarray Sum Equals K – LC 560
- #Continuous Subarray Sum – LC 523
- #Top K Frequent Elements – LC 347
- #Find All Anagrams in a String – LC 438
- #Design HashMap – LC 706
- #Design HashSet – LC 705
- #4Sum II – LC 454
- #Word Pattern – LC 290
Interview focus:
Do you know
HARD (21–30): State Tracking Under Pressure
These test hash design, not syntax.
- #Longest Substring Without Repeating Characters (Hash view) – LC 3
- #LRU Cache – LC 146
- #Count Subarrays Divisible by K – LC 974
- #Count Subarrays with XOR = K – GFG
- #Number of Matching Subsequences – LC 792
- #Find Duplicate Subtrees – LC 652
- #All O(1) Data Structure – LC 432
- #LFU Cache – LC 460
- #First Missing Positive – LC 41
- #Maximum Frequency Stack – LC 895
These require:
- Correct state representation
- Careful memory usage
- Clear invariant explanation
The Question You Must Ask Yourself
Before coding, always ask:
“What exact state do I need to remember?”
Wrong state → wrong solution.
Common Interview Killers
- Hashing the wrong key
- Forgetting to update frequency
- Memory overuse without justification
- Not mentioning time–space tradeoff
INTERVIEW REVISION CARD — Pattern 2
1️⃣ Pattern in One Line
"Store what you've seen so you don't rescan — trade memory for speed."
2️⃣ Recognize It When...
- Brute force uses nested loops checking history
- You need O(1) lookup of past elements
- Trigger words: "first time", "already seen", "frequency", "unique", "duplicate"
- Checking existence, pairs, or cycles
3️⃣ Don't Confuse With...
- Traversal (P1) → when no lookup needed, just scan
- Prefix Sum (P3) → when you need cumulative sums, not lookups
- Two Pointers (P4) → when input is sorted and pointers suffice
4️⃣ Approach in 3 Steps
- #Ask: "What exact state do I need to remember?"
- #Choose: HashMap (key→value), HashSet (existence), frequency array
- #For each element: check map first, then update map
5️⃣ Invariant to Maintain
"At every index i, the map contains all information about arr[0..i-1] needed to answer queries at i."
6️⃣ Complexity to Justify
- Time: O(N) — single pass with O(1) average lookup
- Space: O(N) — map stores up to N entries
- Why: HashMap replaces inner loop entirely
7️⃣ Edge Cases to Always Check
- Empty array/string
- All same elements
- Negative numbers as keys
- Integer overflow in frequency counts
- Empty map at start
8️⃣ One Line to Say in Interview
"I'll use a HashMap to store previously seen state, converting the O(N²) brute force into O(N) by eliminating the inner loop."