Lesson 4 of 8 · 48 min

Hashmaps, prefix sums, and counting

Frequency maps, prefix-sum + hash for subarray sum K, anagram keys, complexity narration, and production counting metaphors.

O(n) memory for O(n) time — the trade builders under-explain

Production engineers use maps constantly (requests per endpoint, sets of ids) but under-explain them in interviews: they code a dict without saying what key means and what invariant the map holds. Hash + prefix patterns convert nested scans into one pass: frequency maps, “have I seen target−x”, prefix sums for range and subarray sum K. Complexity speech: O(n) average time, O(n) space — and when adversarial hashing or sorted alternatives matter.
Three workhorse moves. Frequency map: count occurrences; compare multisets (anagrams). Value→index / value→first-seen: pair problems, first unique. Prefix sum + map of prefix→count/index: subarray sum equals K, contiguous array (0/1 treated as −1/+1), longest subarray with sum K. Production: time-bucketed metrics, cumulative counters, “how many requests since midnight.”
Prefix definition: pref[0]=0; pref[i] = a[0]+…+a[i−1]. Sum of a[l..r−1] = pref[r]−pref[l]. Subarray sum = K ⇔ pref[r] − pref[l] = K ⇔ pref[l] = pref[r]−K. As you compute pref[r], look up how many prior prefixes equal pref[r]−K. That is the whole O(n) idea.

Frequency maps: anagrams and groups

Group Anagrams: key = sorted string or 26-tuple count; map key → list of words. Find All Anagrams in a String: sliding window of |p| with freq match — hybrid of L3+L4. Valid Anagram: one count array, increment/decrement. Narrate key design: collision-free for lowercase letters via 26-int tuple; sorted key is simpler but O(k log k) per word.
python
1GROUP ANAGRAMS — key design is the interview content23from collections import defaultdict45def group_anagrams(strs: list[str]) -> list[list[str]]:6    groups: dict[tuple[int, ...], list[str]] = defaultdict(list)7    for w in strs:8        cnt = [0] * 269        for ch in w:10            cnt[ord(ch) - 97] += 111        groups[tuple(cnt)].append(w)12    return list(groups.values())1314# O(n * k) time for n words length k; space O(n k).15# Sorted-key alternative: key=''.join(sorted(w)) — simpler, slower per word.

Two Sum again — hash as first-class pattern

You saw Two Sum in L1 as rubric. Here it is pure hash pattern: one pass, need = target−x. Variants: all pairs (careful with duplicates), Two Sum BST, Two Sum less than K. Always state if modification of input is allowed (sort+two pointers alternative).

Subarray Sum Equals K

This is the flagship prefix+hash problem. Running sum s; ans += count[s−k]; count[s]++. Initialize count[0]=1 for subarrays from index 0. Negatives allowed — window fails, prefix works. Production metaphor: number of time ranges where error_count increased by K.
python
1SUBARRAY SUM EQUALS K — prefix + hashmap23from collections import defaultdict45def subarray_sum(nums: list[int], k: int) -> int:6    count: dict[int, int] = defaultdict(int)7    count[0] = 18    s = 09    ans = 010    for x in nums:11        s += x12        ans += count[s - k]13        count[s] += 114    return ans1516# Dry-run nums=[1,2,3], k=3:17# x=1 s=1 ans+=count[-2]=0 count={0:1,1:1}18# x=2 s=3 ans+=count[0]=1  -> [1,2]19# x=3 s=6 ans+=count[3]=1  -> [3]; total 2 ✓
Contiguous Array (equal 0s and 1s): map 0→−1, track first index of each prefix; when prefix repeats, subarray between has sum 0 ⇒ equal 0/1. Same family, different payload in the map (index vs count).

Interview complexity speech

Say out loud: average O(n) time for hash ops; worst-case pathological hashing is rare in interviews — they want the average case. Space O(n) for the map. If interviewer asks to reduce space, discuss sort+two pointers when applicable, or streaming approximations (outside classic coding). For “top-K endpoints last hour” → frequency map then heap (next lesson) or counter.most_common — name the structure pipeline.

Order of operations and reconstruction

Lookup-before-insert is non-negotiable for pair and prefix problems. For Two Sum, inserting before lookup can pair an element with itself when 2*x = target. For subarray sum K, inserting before lookup double-counts the empty contribution in some variants. Say the order out loud: “check need, then record current.”
When asked to return the subarray (not the count), store first index of each prefix or keep parent pointers — still O(n). When asked all subarrays, you may need lists of indices per prefix (watch memory). Clarify output shape before choosing map payload.
python
1LONGEST SUBARRAY WITH SUM K (positives only → window; general → prefix index map)23def longest_sum_k_general(nums: list[int], k: int) -> int:4    first: dict[int, int] = {0: -1}  # prefix -> earliest index5    s = 06    best = 07    for i, x in enumerate(nums):8        s += x9        if s - k in first:10            best = max(best, i - first[s - k])11        if s not in first:12            first[s] = i  # keep earliest for longest13    return best1415# Contrast: if all nums > 0, variable window with sum shrink is enough.16# Naming that branch is Problem Solving credit.

Anagram window hybrid

Find All Anagrams is sliding window of fixed width |p| with a freq-diff counter: when diff hits zero, record start. It is L3+L4 fused — fixed window + multiset equality. Interviewers use it to see if you can compose patterns, not just name them in isolation.
Subarray Sum Equals K — explanation style (NeetCode)NeetCode

Interview prep

Hash/prefix rounds test whether you can invent the key meaning under time pressure. Drill: restate subarray-sum-K from the identity pref[r]−pref[l]=K with eyes closed.
  1. 01“Subarray sum equals K with negatives?” → prefix sum + hash count; not sliding window.
  2. 02“Why count[0]=1?” → empty prefix: whole prefix equals K from start.
  3. 03“Group anagrams key?” → 26-count tuple or sorted string; trade O(k) vs O(k log k).
  4. 04“Top-K endpoints last hour?” → freq map in window, then heap of size K (L5).
  5. 05“Two Sum space vs sort?” → hash O(n)/O(n); sort+pointers O(n log n)/O(1) loses indices unless stored.
  6. 06“Contiguous array equal 0/1?” → 0→−1, first-seen prefix index, max length on repeat prefix.
  7. 07“When is window better than prefix?” → non-negative + monotonic constraint on contiguous segment.
  8. 08“What do you say before coding?” → key meaning, update order (lookup then insert), complexity.
  9. 09"Why counts[0]=1?" -> empty prefix so subarrays starting at 0 match when prefix==K.
  10. 10"Anagram key sort vs freq?" -> sort simpler; vector O(k) for fixed alphabet.
  11. 11"Top K heap vs bucket?" -> heap O(n log k); bucket O(n) when freq range is n.
  12. 12"Prefix mod K?" -> same remainder => window sum divisible by K.
  13. 13"Hash vs two pointers for pair sum?" -> unsorted/indices => hash; sorted + O(1) space => two pointers.
  14. 14"Production hash concern?" -> memory overhead, concurrent access, adversarial keys, rehash pauses.
Lookup then insert. Swapping that order on Two Sum or prefix problems double-counts or misses — dry-run one example with the order spoken aloud.
docsPrefix sum techniqueLeetCodearticleAlgoMaster patterns (Prefix Sum)AlgoMasterdocsNeetCode roadmapNeetCodearticleTech Interview Handbook — hash tablesTech Interview Handbook

Prefix+map, anagrams, and production hash realism

Idioms. Complement lookup (Two Sum). Frequency counters (anagrams, majority, top-K). Prefix-sum + map (subarray sum K; init counts[0]=1). Prefix mod K for divisible-by-K. Group anagrams: sorted-tuple key vs char-frequency vector (vector wins for small alphabets). Top K: bucket O(n) vs heap O(n log k). LRU/rate-limiter teasers (full builds in L8): map+DLL; map user->bucket. Production: Python dict ~1.5-2x memory open-addressing; Java HashMap degrades on bad hashes; Go maps not concurrent-safe for mixed R/W; randomized hashing fights adversarial keys. Walk the narrative: partner existence is hash lookup; repeated range sums are prefix; how many windows sum to K is prefix plus frequency of prior prefixes. Dry-run [1,2,3] k=3 with the map evolving: after 1, {0:1,1:1}; after 2, prefix=3 hits 0; after 3, prefix=6 hits 3 — two windows. That dry-run is the Verification score. When n is huge and memory is tight, say you would spill to sort+two-pointers or external sort without abandoning hash for default constraints. Interview drill: on a blank pad, write the evolving prefix map for three arrays — [1,1,1] k=2, [1,-1,0] k=0, and [3,4,7,2,-3,1,4,2] k=7 — before you touch a keyboard. If you cannot predict the answer count from the map alone, you do not own the pattern yet. For group anagrams, say whether the alphabet is lowercase English (vector) or unicode (sort or Counter frozenset). For top-K, if k is close to n, sorting may beat a heap in practice — name the constant-factor tradeoff. LRU and rate-limiter designs are the bridge to L8: the same hash that gives O(1) lookup forces you to pick a second structure for order or time.
python
1SUBARRAY SUM EQUALS K — prefix + hashmap (LC 560)23from collections import defaultdict45def subarray_sum(nums: list[int], k: int) -> int:6    counts: dict[int, int] = defaultdict(int)7    counts[0] = 1  # empty prefix — critical8    prefix = ans = 09    for x in nums:10        prefix += x11        ans += counts[prefix - k]12        counts[prefix] += 113    return ans1415# [1,2,3] k=3 -> 2. Forgetting counts[0]=1 drops index-0 starts.16# Ledger metaphor: balance-K lookup counts windows that sum to K.17# Negatives allowed: same code. If only positives, sliding window is an alt family.
python
1GROUP ANAGRAMS — frequency-tuple key23from collections import defaultdict45def group_anagrams(strs: list[str]) -> list[list[str]]:6    buckets: dict[tuple, list[str]] = defaultdict(list)7    for s in strs:8        freq = [0] * 269        for ch in s:10            freq[ord(ch) - 97] += 111        buckets[tuple(freq)].append(s)12    return list(buckets.values())1314# Alt key=tuple(sorted(s)): simpler, O(k log k) per string. State tradeoff.15# Unicode input: Counter(s) items sorted into a tuple, or sorted(s) if comparable.
Graders + tiers. Name complement vs prefix+map; when hash loses to two pointers (sorted O(1) space); counts[0]=1; no list keys; edges empty/single/zeros/negatives. FAANG mixes two-sum with design (LRU). India OA: LC 1/49/560 speed. AI lab: sharded maps, bloom false positives, concurrent maps. Stripe-style risk systems and CDN caches are the production stories to name unprompted when they ask why hash. Complexity must include average vs worst hash under adversarial keys if the company is security-sensitive. Resources to keep open while drilling: NeetCode arrays/hashing playlist, TIH patterns, and the LeetCode discuss thread on subarray-sum-equals-k general guidance. Also drill LC 525 Contiguous Array and LC 974 Subarray Sums Divisible by K as the same ledger shape with a transformed value (0/1 as -1/+1, or prefix mod K). If you can reduce a new prompt to ledger + map in under two minutes, the pattern is installed.
Subarray Sum Equals K — NeetCodeNeetCodearticlePrefix sum technique — takeUforwardtakeUforward

Checkpoint

Array may contain negatives. Count subarrays with sum = K. Approach?

ASliding window growing while sum < KBPrefix sum + hashmap of prefix counts; ans += count[s−K]; then count[s]++CSort array then two pointers
Sign up free to answer and see why

Checkpoint

You implement subarray sum K but forget count[0]=1. Which case fails?

AOnly empty inputBSubarrays that start at index 0 with sum exactly KCOnly negative K
Sign up free to answer and see why

Checkpoint

Interview: “top-K most frequent API endpoints in the last hour.” Structure sketch?

AOnly a heap of endpoints, no countsBFrequency map (endpoint→count) over the hour window, then min-heap of size K by count (or counter top-K)CSort all endpoints alphabetically
Sign up free to answer and see why

Checkpoint

Group Anagrams: interviewer asks why not use the string itself as map key.

ABecause strings are immutable in Python so cannot be keysBAnagrams are different strings — you need a canonical key (sorted / count tuple) so they collide into one bucketCYou must use hashing of hashcodes of chars only
Sign up free to answer and see why

Checkpoint

You say “O(n) hash map” — interviewer asks worst case. Best senior reply?

AHash maps are always O(1); worst case does not existBAverage O(1) ops / O(n) total; pathological collisions are rare in interviews; if required we can discuss sort-based alternatives or tree maps O(log n)CSwitch immediately to O(n²) nested loops to avoid hashes
Sign up free to answer and see why

Can you derive subarray sum K from the prefix identity on a whiteboard without notes?

New to itGetting thereConfident

Takeaways

  • Name the map key invariant before coding.
  • Prefix[r]−prefix[l]=K → lookup prefix[r]−K in a count map.
  • count[0]=1; lookup then insert.
  • Negatives kill sum windows; use prefix+hash.
  • Freq map → heap is the top-K metrics pipeline.

Next: intervals and heaps — merge intervals, meeting rooms, top-K, streaming median sketch.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free