Chapter 3a — HashMap Problem Patterns

You now understand what a HashMap is at the physical level. This chapter is about developing the instinct for when to reach for one and exactly how to apply it. There are five patterns that cover the overwhelming majority of HashMap interview problems. Master these five and you will be able to handle nearly any problem in this category — not because you memorized solutions, but because you can see the structure underneath and reconstruct the approach from first principles.

Every problem here is solved with the four-question framework. Every solution has a complete dry run. Nothing is skipped.

The Five HashMap Patterns

Before any problem, here is the pattern map. A signal in the problem statement maps to a pattern. A pattern maps to a technique.

Pattern 1 — Frequency Counting Signal: "how many times does X appear", "find duplicates", "check if two things are rearrangements of each other", "most/least frequent element". Technique: iterate once, count occurrences in a Map. Then use those counts.

Pattern 2 — Complement Lookup Signal: "find two/three/four elements that sum to target", "find pair/triplet satisfying condition", "count subarrays with property". Technique: at each element, compute what you need (the complement). Look it up in a Map. If found, done. If not, store the current element for future lookups.

Pattern 3 — Grouping / Bucketing Signal: "group elements that share a property", "find all X that are related to each other by some transformation". Technique: define a canonical key that all elements in the same group share. Use a Map from canonical key → list of elements.

Pattern 4 — Membership / Seen Set Signal: "find something that exists in the collection", "longest/shortest sequence you can build from given elements", "check if you have visited before". Technique: load all elements into a Set first (O(n) build), then answer membership queries in O(1). The key insight is separating the build phase from the query phase.

Pattern 5 — Prefix Sum + HashMap Signal: "count subarrays with sum/property = k", "find subarray where something balances", "longest subarray with equal count of X and Y". Technique: maintain a running value (sum, count difference, etc.) in a Map as you go. At each position, look up whether a previously seen value would pair with the current one to satisfy the condition.

Pattern 1: Frequency Counting

Problem 1: Valid Anagram (LeetCode 242)

Problem: Given two strings s and t, return true if t is an anagram of s — meaning t contains exactly the same characters in the same frequencies, just possibly in different order.

Input:  s = "anagram", t = "nagaram"
Output: true

Input:  s = "rat", t = "car"
Output: false

Q1: What do I have? Two strings of lowercase English letters. Length can be up to 5×10⁴.

Q2: What do I want? A boolean: do both strings have identical character frequency distributions?

Q3: Brute force? Sort both strings and compare. If sort(s) === sort(t), they are anagrams. O(n log n) time, O(n) space.

This works and is acceptable in interviews. But it misses the deeper pattern.

Q4: Where is the waste? Sorting carries out more work than we need. We do not need the characters in order — we just need to know whether each character appears the same number of times in both strings. Counting is O(n). Comparing counts is O(26) = O(1) for lowercase letters.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const count = new Map();

  // Count characters in s
  for (const ch of s) {
    count.set(ch, (count.get(ch) || 0) + 1);
  }

  // Subtract counts using t
  for (const ch of t) {
    if (!count.has(ch)) return false;
    count.set(ch, count.get(ch) - 1);
    if (count.get(ch) < 0) return false;  // t has more of this char than s
  }

  return true;
}

Full dry run on s = "anagram", t = "nagaram":

Pass 1 — count characters in s:

'a': count = {a:1}
'n': count = {a:1, n:1}
'a': count = {a:2, n:1}
'g': count = {a:2, n:1, g:1}
'r': count = {a:2, n:1, g:1, r:1}
'a': count = {a:3, n:1, g:1, r:1}
'm': count = {a:3, n:1, g:1, r:1, m:1}

Pass 2 — subtract using t = "nagaram":

'n': count.get('n')=1, set to 0.  {a:3, n:0, g:1, r:1, m:1}
'a': count.get('a')=3, set to 2.  {a:2, n:0, g:1, r:1, m:1}
'g': count.get('g')=1, set to 0.  {a:2, n:0, g:0, r:1, m:1}
'a': count.get('a')=2, set to 1.  {a:1, n:0, g:0, r:1, m:1}
'r': count.get('r')=1, set to 0.  {a:1, n:0, g:0, r:0, m:1}
'a': count.get('a')=1, set to 0.  {a:0, n:0, g:0, r:0, m:1}
'm': count.get('m')=1, set to 0.  {a:0, n:0, g:0, r:0, m:0}

No count went negative. Return true ✓

Why check count.get(ch) < 0 instead of checking if all values are zero at the end? The early return makes the algorithm fail fast. If t has a character that s does not have, or t has more of a character than s, we catch it immediately instead of completing the second pass. The s.length !== t.length check at the start eliminates the case where t is longer than s (would otherwise have unused extra characters without triggering the negative check).

Complexity: O(n) time, O(1) space — the Map has at most 26 entries for lowercase English letters regardless of input length.

Problem 2: Top K Frequent Elements (LeetCode 347)

Problem: Given an integer array nums and integer k, return the k most frequent elements. You may return the answer in any order.

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Q1: What do I have? An array of n integers. An integer k ≤ number of unique elements. The answer always exists.

Q2: What do I want? The k elements with the highest frequency.

Q3: Brute force? Count frequencies in a Map, then sort by frequency descending, then take first k. O(n log n) — the sort dominates.

Q4: Where is the waste? We do not need the elements sorted by frequency — we just need the top k. Sorting gives us a full ordering we do not need. There is a technique called bucket sort that exploits a constraint: the maximum possible frequency is n (if all elements are the same). So frequencies live in the range [1, n]. We can create an array of n+1 buckets where bucket[freq] holds all elements with that frequency. Then scan from the highest bucket down, collecting elements until we have k.

This runs in O(n) time — no sorting.

function topKFrequent(nums, k) {
  // Step 1: count frequencies
  const freq = new Map();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }

  // Step 2: bucket sort — index is frequency, value is list of numbers
  const buckets = new Array(nums.length + 1).fill(null).map(() => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

  // Step 3: collect top k from highest frequency bucket down
  const result = [];
  for (let i = buckets.length - 1; i >= 1 && result.length < k; i--) {
    for (const num of buckets[i]) {
      result.push(num);
      if (result.length === k) break;
    }
  }

  return result;
}

Full dry run on nums = [1, 1, 1, 2, 2, 3], k = 2:

Step 1 — frequency count:

num=1: freq={1:1}
num=1: freq={1:2}
num=1: freq={1:3}
num=2: freq={1:3, 2:1}
num=2: freq={1:3, 2:2}
num=3: freq={1:3, 2:2, 3:1}

Step 2 — place into buckets (array length = 6+1 = 7):

Element 1 has freq 3 → buckets[3] = [1]
Element 2 has freq 2 → buckets[2] = [2]
Element 3 has freq 1 → buckets[1] = [3]

buckets = [[], [3], [2], [1], [], [], []]
             ↑0   ↑1   ↑2   ↑3  ↑4  ↑5  ↑6

Step 3 — collect from highest bucket:

i=6: buckets[6]=[] → skip
i=5: buckets[5]=[] → skip
i=4: buckets[4]=[] → skip
i=3: buckets[3]=[1] → push 1. result=[1]. length=1 < k=2.
i=2: buckets[2]=[2] → push 2. result=[1,2]. length=2 = k. Stop.

Return [1, 2] ✓

Why does bucket sort work here? The frequency of any element is bounded by n (cannot exceed total elements). This gives us a bounded range, which is exactly when bucket sort is applicable. We trade O(n log n) sorting (unknown range) for O(n) bucket placement (bounded range). The bucket array costs O(n) space, but we needed O(n) space for the frequency Map already.

Complexity: O(n) time, O(n) space.

Pattern 2: Complement Lookup

Problem 3: Two Sum (LeetCode 1)

This is the most foundational HashMap problem. Every complement-lookup problem is a generalization of this one.

Problem: Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]   (nums[0] + nums[1] = 2 + 7 = 9)

Q1: What do I have? An array of n integers. A target integer. Guaranteed exactly one solution.

Q2: What do I want? The two indices (not values) that sum to target.

Q3: Brute force? Every pair: O(n²).

Q4: Where is the waste?

For each element nums[i], the brute force searches the entire remaining array for target - nums[i]. That search is O(n).

Replace the search with a Map lookup: O(1).

As you scan: at index i, you need target - nums[i]. Ask the Map: "have I seen this value before?" If yes, return its stored index and i. If no, store nums[i] → i in the Map and move on.

function twoSum(nums, target) {
  const seen = new Map();  // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }

    seen.set(nums[i], i);
  }
}

Full dry run on nums = [2, 7, 11, 15], target = 9:

seen = {}

i=0: nums[0]=2. complement = 9-2 = 7.
  seen.has(7)? NO.
  seen.set(2, 0) → seen = {2:0}

i=1: nums[1]=7. complement = 9-7 = 2.
  seen.has(2)? YES. seen.get(2) = 0.
  Return [0, 1] ✓

Dry run on a trickier input nums = [3, 2, 4], target = 6:

seen = {}

i=0: nums[0]=3. complement = 6-3 = 3.
  seen.has(3)? NO. (3 is not yet in the map — we haven't stored it yet)
  seen.set(3, 0) → seen = {3:0}

i=1: nums[1]=2. complement = 6-2 = 4.
  seen.has(4)? NO.
  seen.set(2, 1) → seen = {3:0, 2:1}

i=2: nums[2]=4. complement = 6-4 = 2.
  seen.has(2)? YES. seen.get(2) = 1.
  Return [1, 2] ✓

Why do we check the Map BEFORE storing the current element? Consider nums = [3, 3], target = 6. If we stored first and then checked, at i=0 we would store 3→0, then check for complement 3 — find it, and return [0, 0]. But a single element cannot pair with itself. By checking first, then storing: at i=0 we check for 3 — not found, then store 3→0. At i=1 we check for 3 — found at index 0, return [0, 1]. Correct.

Complexity: O(n) time, O(n) space.

Problem 4: 4Sum II (LeetCode 454)

Problem: Given four integer arrays A, B, C, D each of length n, return the number of tuples (i, j, k, l) such that A[i] + B[j] + C[k] + D[l] = 0.

Input:  A=[1,-2], B=[-2,1], C=[-1,2], D=[0,2]
Output: 2

Why this problem matters: It looks like it requires four nested loops (O(n⁴)). The HashMap insight cuts it to O(n²). The technique — "split the problem, store half, look up the other half" — generalizes to any kSum problem.

Q1: What do I have? Four arrays, each length n. n up to 200. Values can be anything.

Q2: What do I want? A count of quadruples summing to 0.

Q3: Brute force? Four nested loops. O(n⁴). For n=200, that is 1.6 billion iterations. Too slow.

Q4: Where is the waste?

Instead of four loops, use two loops of two:

• Compute all A[i] + B[j] sums. Store in a Map with their frequency.
• Compute all C[k] + D[l] sums. For each, look up -(C[k] + D[l]) in the Map.

This is the complement trick applied to pairs instead of singles.

function fourSumCount(A, B, C, D) {
  const abSums = new Map();

  // Store all pairwise sums from A and B
  for (const a of A) {
    for (const b of B) {
      const sum = a + b;
      abSums.set(sum, (abSums.get(sum) || 0) + 1);
    }
  }

  let count = 0;

  // For each pair from C and D, look up its complement in AB sums
  for (const c of C) {
    for (const d of D) {
      const complement = -(c + d);
      if (abSums.has(complement)) {
        count += abSums.get(complement);
      }
    }
  }

  return count;
}

Full dry run on A=[1,-2], B=[-2,1], C=[-1,2], D=[0,2]:

Step 1 — all A+B pairs:

(a=1,  b=-2): sum = -1. abSums = {-1:1}
(a=1,  b= 1): sum =  2. abSums = {-1:1, 2:1}
(a=-2, b=-2): sum = -4. abSums = {-1:1, 2:1, -4:1}
(a=-2, b= 1): sum = -1. abSums = {-1:2, 2:1, -4:1}  ← -1 appears twice

Step 2 — all C+D pairs, looking up complement:

(c=-1, d=0): sum=-1. complement=1.  abSums.has(1)? NO.
(c=-1, d=2): sum=1.  complement=-1. abSums.has(-1)? YES, count=2. count+=2 → count=2.
(c= 2, d=0): sum=2.  complement=-2. abSums.has(-2)? NO.
(c= 2, d=2): sum=4.  complement=-4. abSums.has(-4)? YES, count=1. count+=1 → count=3.

Wait — expected output is 2. Let me recheck the input.

A=[1,-2], B=[-2,1], C=[-1,2], D=[0,2]

The actual valid tuples are those where A[i]+B[j]+C[k]+D[l]=0:

• (1) + (-2) + (-1) + (2) = 0 → valid (i=0,j=0,k=0,l=1)
• (1) + (-2) + (2) + (-1)... wait D doesn't have -1.

Let me enumerate:

A[0]+B[0]+C[0]+D[0] = 1+(-2)+(-1)+0 = -2 ≠ 0
A[0]+B[0]+C[0]+D[1] = 1+(-2)+(-1)+2 = 0  ✓
A[0]+B[0]+C[1]+D[0] = 1+(-2)+2+0 = 1 ≠ 0
A[0]+B[0]+C[1]+D[1] = 1+(-2)+2+2 = 3 ≠ 0
A[0]+B[1]+C[0]+D[0] = 1+1+(-1)+0 = 1 ≠ 0
A[0]+B[1]+C[0]+D[1] = 1+1+(-1)+2 = 3 ≠ 0
A[0]+B[1]+C[1]+D[0] = 1+1+2+0 = 4 ≠ 0
A[0]+B[1]+C[1]+D[1] = 1+1+2+2 = 6 ≠ 0
A[1]+B[0]+C[0]+D[0] = -2+(-2)+(-1)+0 = -5 ≠ 0
A[1]+B[0]+C[0]+D[1] = -2+(-2)+(-1)+2 = -3 ≠ 0
A[1]+B[0]+C[1]+D[0] = -2+(-2)+2+0 = -2 ≠ 0
A[1]+B[0]+C[1]+D[1] = -2+(-2)+2+2 = 0  ✓
A[1]+B[1]+C[0]+D[0] = -2+1+(-1)+0 = -2 ≠ 0
A[1]+B[1]+C[0]+D[1] = -2+1+(-1)+2 = 0  ✓ 
A[1]+B[1]+C[1]+D[0] = -2+1+2+0 = 1 ≠ 0
A[1]+B[1]+C[1]+D[1] = -2+1+2+2 = 3 ≠ 0

Three valid tuples. But expected answer is 2. Let me re-examine — I may have the wrong example. The classic 4Sum II example from LeetCode:

A = [1,2], B = [-2,-1], C = [-1,2], D = [0,2]
Output: 2

Let me redo with this canonical input:

Full dry run on A=[1,2], B=[-2,-1], C=[-1,2], D=[0,2]:

Step 1 — all A+B pairs:

(1,-2): sum=-1. abSums={-1:1}
(1,-1): sum= 0. abSums={-1:1, 0:1}
(2,-2): sum= 0. abSums={-1:1, 0:2}
(2,-1): sum= 1. abSums={-1:1, 0:2, 1:1}

Step 2 — all C+D pairs, looking up complement (0 - (c+d)):

(c=-1,d=0): c+d=-1. complement=1.  abSums.has(1)? YES, freq=1. count+=1 → count=1.
(c=-1,d=2): c+d=1.  complement=-1. abSums.has(-1)? YES, freq=1. count+=1 → count=2.
(c= 2,d=0): c+d=2.  complement=-2. abSums.has(-2)? NO.
(c= 2,d=2): c+d=4.  complement=-4. abSums.has(-4)? NO.

Return 2 ✓

Why does count += abSums.get(complement) instead of count += 1? Because there may be multiple AB pairs with the same sum. Each of those pairs, combined with the current CD pair, forms a distinct valid tuple. The frequency in the Map tells us how many distinct AB pairs give that sum.

Complexity: O(n²) time (two passes of nested loops), O(n²) space for the AB sums Map (at most n² unique sums from n×n pairs).

The general principle: When a problem requires k elements from k arrays summing to a target, split k into two halves, compute all sums for each half, and use a HashMap to find complement pairs. This pattern halves the exponent: O(n⁴) → O(n²), O(n³) → O(n^{1.5}) approximately.

Pattern 3: Grouping / Bucketing

Problem 5: Group Anagrams (LeetCode 49)

This is the #9 most-asked LeetCode problem globally. It appears at Google, Amazon, Meta, Razorpay, and Goldman Sachs.

Problem: Given an array of strings strs, group the anagrams together. You may return the answer in any order.

Input:  ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Q1: What do I have? An array of n strings, each of length at most k. n up to 10⁴, k up to 100.

Q2: What do I want? Groups of strings where all strings in a group are anagrams of each other.

Q3: Brute force? For each string, compare it with every other string to check if they are anagrams. O(n² × k). All strings that are anagrams of each other go into the same group.

Q4: Where is the waste?

Two strings are anagrams if and only if they have the same character frequency distribution. So define a canonical key that all anagrams share. Any string's canonical key maps to exactly one group.

Two canonical key options:

Option A — Sorted string: Sort the characters of each string. "eat" → "aet", "tea" → "aet", "tan" → "ant". All anagrams sort to the same string.

Option B — Character count tuple: Represent each string as a count of each character: [count_a, count_b, ..., count_z]. "eat" → [1,0,0,0,1,0,...,1,0,0,0] (1 'a', 1 'e', 1 't'). Anagrams produce identical tuples.

Option A costs O(k log k) per string. Option B costs O(k) per string, O(1) for the key comparison. For this problem, both are acceptable.

function groupAnagrams(strs) {
  const groups = new Map();  // canonical key → [list of anagrams]

  for (const s of strs) {
    // Canonical key: sorted characters joined as string
    const key = s.split('').sort().join('');

    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key).push(s);
  }

  return Array.from(groups.values());
}

Full dry run on ["eat","tea","tan","ate","nat","bat"]:

s="eat": key = ['e','a','t'].sort() = ['a','e','t'] → "aet"
  groups = {"aet": ["eat"]}

s="tea": key = ['t','e','a'].sort() = ['a','e','t'] → "aet"
  "aet" exists → groups = {"aet": ["eat","tea"]}

s="tan": key = ['t','a','n'].sort() = ['a','n','t'] → "ant"
  groups = {"aet": ["eat","tea"], "ant": ["tan"]}

s="ate": key = ['a','t','e'].sort() = ['a','e','t'] → "aet"
  groups = {"aet": ["eat","tea","ate"], "ant": ["tan"]}

s="nat": key = ['n','a','t'].sort() = ['a','n','t'] → "ant"
  groups = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"]}

s="bat": key = ['b','a','t'].sort() = ['a','b','t'] → "abt"
  groups = {"aet": ["eat","tea","ate"], "ant": ["tan","nat"], "abt": ["bat"]}

Return [["eat","tea","ate"], ["tan","nat"], ["bat"]] ✓

Why is choosing the right canonical key the entire problem? Once you have a key that uniquely identifies the equivalence class (all anagrams), the grouping is trivial — just a Map. The intellectual work is figuring out what property all members of a group share. For anagrams: same character frequencies → sorted string or count array are both valid keys. For other grouping problems, the key design changes. Group Shifted Strings uses the difference sequence between adjacent characters as the key. Find Duplicate Files uses (file content) as the key.

Complexity: O(n × k log k) for sorted key approach, O(n × k) for count array approach. Space: O(n × k) for storing all strings in the Map.

Pattern 4: Membership / Seen Set

Problem 6: Longest Consecutive Sequence (LeetCode 128)

This problem is asked at Google, Amazon, and Facebook. The O(n) solution is non-obvious — most people start with sorting (O(n log n)) and need to be pushed toward the Set approach.

Problem: Given an unsorted array of integers, return the length of the longest consecutive elements sequence.

Input:  [100, 4, 200, 1, 3, 2]
Output: 4
Reason: [1, 2, 3, 4] is the longest consecutive sequence.

Constraint: Must run in O(n) time.

Q1: What do I have? An unsorted array of n integers. Values can be anything.

Q2: What do I want? The length of the longest run of consecutive integers (e.g., 5, 6, 7, 8 is a run of length 4).

Q3: Brute force / obvious approach? Sort the array. Scan linearly, counting consecutive runs. O(n log n). Correct, but the constraint says O(n).

Q4: Where is the waste in the sorted approach? Sorting gives us more than we need. We do not care about the order of the array — we only care about membership: "given a number x, does x+1 exist in the array?" If we could answer this in O(1), we could find consecutive sequences in O(n).

Load all numbers into a Set. Now membership checks are O(1).

But there is still a trap: if you start counting a sequence from every element, you recount sequences. If [1,2,3,4] is a sequence and you start from 1, 2, 3, and 4, you count the length-4 sequence four times.

The fix: only start counting a sequence from a number that has no left neighbor. A number x is the start of a sequence if and only if x-1 is not in the Set.

function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let longest = 0;

  for (const num of numSet) {
    // Only start counting if num is the beginning of a sequence
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let length = 1;

      while (numSet.has(currentNum + 1)) {
        currentNum++;
        length++;
      }

      longest = Math.max(longest, length);
    }
  }

  return longest;
}

Full dry run on [100, 4, 200, 1, 3, 2]:

Build Set:

numSet = {100, 4, 200, 1, 3, 2}

Iterate — note we iterate over the Set (any order, but let's say: 100, 4, 200, 1, 3, 2):

num=100: numSet.has(99)? NO → start of sequence.
  currentNum=100, length=1
  numSet.has(101)? NO → stop.
  longest = max(0, 1) = 1

num=4: numSet.has(3)? YES → not a sequence start. Skip.

num=200: numSet.has(199)? NO → start of sequence.
  currentNum=200, length=1
  numSet.has(201)? NO → stop.
  longest = max(1, 1) = 1

num=1: numSet.has(0)? NO → start of sequence.
  currentNum=1, length=1
  numSet.has(2)? YES → currentNum=2, length=2
  numSet.has(3)? YES → currentNum=3, length=3
  numSet.has(4)? YES → currentNum=4, length=4
  numSet.has(5)? NO → stop.
  longest = max(1, 4) = 4

num=3: numSet.has(2)? YES → not a start. Skip.

num=2: numSet.has(1)? YES → not a start. Skip.

Return 4 ✓

Why is this O(n) despite the while loop inside the for loop?

The while loop extends along a consecutive sequence. Each number in the array is visited at most twice — once when we encounter it in the outer for loop (where we skip it if it is not a sequence start), and once inside the while loop when it is part of a sequence starting at some earlier number. Total inner loop iterations across all outer iterations ≤ n. So the total work is O(n) — the nested loop is not O(n²) because the inner iterations do not reset.

This is an important pattern: apparent O(n²) that is actually O(n) because each element is visited a bounded total number of times across all inner loop executions.

Complexity: O(n) time, O(n) space for the Set.

Pattern 5: Prefix + HashMap

Problem 7: Contiguous Array (LeetCode 525)

This is a brilliant application of the prefix + HashMap pattern. It looks like it has nothing to do with prefix sums — until you see the transformation.

Problem: Given a binary array nums (containing only 0s and 1s), return the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Input:  [0, 1, 0]
Output: 2
Reason: [0, 1] or [1, 0] — each has one 0 and one 1.

Q1: What do I have? An array of 0s and 1s. Length up to 5×10⁴.

Q2: What do I want? The length of the longest contiguous subarray where count(0s) == count(1s).

Q3: Brute force? All subarrays: count 0s and 1s in each. O(n²) or O(n³).

Q4: Where is the waste?

The key transformation: replace every 0 with -1. Now the condition "equal 0s and 1s" becomes "subarray sum = 0" (because each 1 contributes +1 and each -1 (formerly 0) contributes -1; they cancel out when equal in count).

"Longest subarray with sum = 0" is a classic prefix sum + HashMap problem. We want the longest subarray [i+1..j] where prefix[j] - prefix[i] = 0, i.e., prefix[j] = prefix[i].

Store the first occurrence of each prefix sum in a HashMap. When we see the same prefix sum again at index j, the subarray between the first occurrence and j sums to 0. Track the maximum such length.

function findMaxLength(nums) {
  // Map from prefix sum → first index where this prefix sum occurred
  const firstSeen = new Map();
  firstSeen.set(0, -1);  // prefix sum 0 occurs "before" index 0

  let prefixSum = 0;
  let maxLen = 0;

  for (let i = 0; i < nums.length; i++) {
    prefixSum += (nums[i] === 1) ? 1 : -1;  // treat 0 as -1

    if (firstSeen.has(prefixSum)) {
      // Same prefix sum seen before — subarray between then and now sums to 0
      maxLen = Math.max(maxLen, i - firstSeen.get(prefixSum));
    } else {
      // First time seeing this prefix sum — record it
      firstSeen.set(prefixSum, i);
    }
  }

  return maxLen;
}

Full dry run on [0, 1, 0]:

Transform: treat 0 as -1. Effective array: [-1, 1, -1].

firstSeen = {0: -1},  prefixSum = 0,  maxLen = 0

i=0: nums[0]=0 → contribution=-1. prefixSum = 0+(-1) = -1.
  firstSeen.has(-1)? NO.
  firstSeen.set(-1, 0) → firstSeen = {0:-1, -1:0}

i=1: nums[1]=1 → contribution=+1. prefixSum = -1+1 = 0.
  firstSeen.has(0)? YES. firstSeen.get(0) = -1.
  length = i - firstSeen.get(0) = 1 - (-1) = 2.
  maxLen = max(0, 2) = 2.
  (Note: we do NOT update firstSeen — we keep the FIRST occurrence to maximize length)

i=2: nums[2]=0 → contribution=-1. prefixSum = 0+(-1) = -1.
  firstSeen.has(-1)? YES. firstSeen.get(-1) = 0.
  length = i - firstSeen.get(-1) = 2 - 0 = 2.
  maxLen = max(2, 2) = 2.

Return 2 ✓

Why firstSeen.set(0, -1) (sentinel at index -1)?

If the entire prefix from index 0 to index j sums to 0 (equal 0s and 1s from the start), the subarray is [0..j] with length j - (-1) = j + 1. Without the sentinel, we would miss this case — we would not find a previous occurrence of prefix sum 0 and would not compute the length.

Why do we NOT update firstSeen when we see a duplicate prefix sum? Because we want the longest subarray. A prefix sum first seen at index 3 and again at index 7 gives a subarray of length 4. A prefix sum first seen at index 3 and again at index 10 gives a subarray of length 7. Keeping the first occurrence maximizes the distance to any future recurrence.

Complexity: O(n) time, O(n) space.

The deeper insight: The "replace values with +1/-1 to convert balance to sum" technique works for any "count of A equals count of B" problem. Binary strings (0 and 1), characters ('a' and 'b'), open and close parentheses — all can be encoded as +1/-1 and reduced to "longest subarray with sum 0."

Problem 8: Find All Anagrams in a String (LeetCode 438) — Sliding Window + HashMap Preview

This problem bridges HashMap patterns into Sliding Window territory (Chapter 6). It is included here because the HashMap is doing the core work — the sliding window is just the mechanism to move efficiently.

Problem: Given strings s and p, return all starting indices of p's anagrams in s.

Input:  s = "cbaebabacd", p = "abc"
Output: [0, 6]
Reason: s[0..2] = "cba" is an anagram of "abc". s[6..8] = "bac" is an anagram of "abc".

Q1: What do I have? String s (length n), pattern p (length k). Find all windows of size k in s that are anagrams of p.

Q2: What do I want? A list of starting indices.

Q3: Brute force? For each starting index i in s, sort s[i..i+k-1] and compare to sorted p. O(n × k log k).

Q4: Where is the waste? Recomputing frequencies from scratch for each window. When the window slides one position right, one character leaves and one enters. We can update the frequency Map in O(1) instead of recomputing in O(k).

Maintain:

• pCount: frequency Map for pattern p (fixed)
• windowCount: frequency Map for the current window (updated as window slides)
• matches: count of characters where windowCount matches pCount

When matches === number of unique characters in p, the current window is an anagram.

function findAnagrams(s, p) {
  if (s.length < p.length) return [];

  const pCount = new Map();
  const windowCount = new Map();
  const result = [];

  // Build pCount
  for (const ch of p) {
    pCount.set(ch, (pCount.get(ch) || 0) + 1);
  }

  const k = p.length;
  let matches = 0;  // how many chars have matching frequency

  // Initialize first window
  for (let i = 0; i < k; i++) {
    const ch = s[i];
    windowCount.set(ch, (windowCount.get(ch) || 0) + 1);
  }

  // Count initial matches
  for (const [ch, count] of pCount) {
    if (windowCount.get(ch) === count) matches++;
  }

  if (matches === pCount.size) result.push(0);

  // Slide the window
  for (let i = k; i < s.length; i++) {
    const incoming = s[i];
    const outgoing = s[i - k];

    // Add incoming character
    windowCount.set(incoming, (windowCount.get(incoming) || 0) + 1);
    // Did this char's count now match or unmatch pCount?
    if (pCount.has(incoming)) {
      if (windowCount.get(incoming) === pCount.get(incoming)) matches++;
      else if (windowCount.get(incoming) === pCount.get(incoming) + 1) matches--;
    }

    // Remove outgoing character
    windowCount.set(outgoing, windowCount.get(outgoing) - 1);
    if (pCount.has(outgoing)) {
      if (windowCount.get(outgoing) === pCount.get(outgoing)) matches++;
      else if (windowCount.get(outgoing) === pCount.get(outgoing) - 1) matches--;
    }

    if (matches === pCount.size) result.push(i - k + 1);
  }

  return result;
}

Dry run on s = "cbaebabacd", p = "abc":

pCount = {c:1, b:1, a:1}. k=3.

Initial window s[0..2] = "cba":
windowCount = {c:1, b:1, a:1}
matches = 3 (all three chars match pCount exactly)
matches === pCount.size(3) → push 0. result=[0]

i=3, incoming=s[3]='e', outgoing=s[0]='c':
  Add 'e': windowCount={c:1,b:1,a:1,e:1}. 'e' not in pCount → no change to matches.
  Remove 'c': windowCount={c:0,b:1,a:1,e:1}.
    pCount.has('c')? YES. windowCount['c']=0 which is pCount['c']-1=0 → matches++? 
    Wait: we just went from 1 to 0. pCount['c']=1. New count=0 ≠ 1 → was it matching before?
    Before removal, windowCount['c']=1 = pCount['c']=1 → was matching.
    After removal, windowCount['c']=0 ≠ pCount['c']=1 → no longer matching.
    So matches-- → matches=2.
  matches(2) ≠ pCount.size(3) → no push.

i=4, incoming=s[4]='b', outgoing=s[1]='b':
  Add 'b': windowCount={c:0,b:2,a:1,e:1}. 
    pCount.has('b')? YES. windowCount['b']=2, pCount['b']=1.
    2 === 1+1 → was matching (1==1) now overshot → matches-- → matches=1.
  Remove 'b': windowCount={c:0,b:1,a:1,e:1}.
    pCount.has('b')? YES. windowCount['b']=1 = pCount['b']=1 → now matches → matches++ → matches=2.
  matches(2) ≠ 3 → no push.

i=5, incoming=s[5]='a', outgoing=s[2]='a':
  Add 'a': windowCount['a']=2. pCount['a']=1. 2===1+1 → was matching, overshot → matches-- → matches=1.
  Remove 'a': windowCount['a']=1 = pCount['a']=1 → matches++ → matches=2.
  matches(2) ≠ 3 → no push.

i=6, incoming=s[6]='b', outgoing=s[3]='e':
  Add 'b': windowCount['b']=2. pCount['b']=1. overshot → matches-- → matches=1.
  Remove 'e': 'e' not in pCount → no change to matches.
  matches(1) ≠ 3 → no push.

i=7, incoming=s[7]='a', outgoing=s[4]='b':
  Add 'a': windowCount['a']=2. overshot → matches-- → matches=0.
  Remove 'b': windowCount['b']=1 = pCount['b']=1 → matches++ → matches=1.
  matches(1) ≠ 3 → no push.

i=8, incoming=s[8]='c', outgoing=s[5]='a':
  Add 'c': windowCount['c']=1 = pCount['c']=1 → matches++ → matches=2.
  Remove 'a': windowCount['a']=1 = pCount['a']=1 → back to matching → matches++ → matches=3.
  
  Wait, before removal: windowCount['a']=2. After removal: windowCount['a']=1 = pCount['a']=1.
  Before removal, was 'a' matching? 2 ≠ 1 → NO. After removal, 1=1 → YES → matches++ → matches=3.
  
  matches(3) === pCount.size(3) → push i-k+1 = 8-3+1 = 6. result=[0,6].

i=9, incoming=s[9]='d', outgoing=s[6]='b':
  Add 'd': not in pCount → no change.
  Remove 'b': windowCount['b']=0 ≠ 1 → was matching, now not → matches-- → matches=2.
  matches ≠ 3 → no push.

Return [0, 6] ✓

Why track matches instead of re-comparing Maps? Comparing two Maps for equality at every step would be O(k). The matches counter tracks equality incrementally — updating in O(1) when a character's count crosses into or out of the "matching" state. This makes the slide O(1) per step, giving O(n) overall.

Complexity: O(n + k) time, O(k) space.

Pattern Recognition Decision Tree

You have a HashMap/Set problem. Ask:

1. Does the problem ask about FREQUENCY (how many times, most common, anagram)?
   → Pattern 1: Frequency Counting (Valid Anagram, Top K Frequent)

2. Does it ask you to FIND A PAIR/TUPLE summing to target?
   → Pattern 2: Complement Lookup (Two Sum, 4Sum II)

3. Does it ask you to GROUP elements sharing a property?
   → Pattern 3: Grouping/Bucketing (Group Anagrams)
   → Ask: what canonical key identifies the group?

4. Does it ask for the LONGEST/SHORTEST SEQUENCE you can build from given elements?
   → Pattern 4: Seen Set + Start-of-Sequence Check (Longest Consecutive)

5. Does it ask to COUNT or FIND subarrays with a sum/balance property?
   → Pattern 5: Prefix + HashMap
   → Ask: what running value, stored at what index, lets me compute the answer?

6. Does it involve a SLIDING WINDOW over characters/elements?
   → Combine a window with a HashMap tracking window state (Find Anagrams)
   → Full treatment in Chapter 6.

Vocabulary Map

Practice Problems

Problem 1 — Trace and Predict

Trace through the following twoSum call by hand:

twoSum([3, 3], target = 6)

Write the exact state of seen after each iteration. What does the function return, and at which iteration?

Now trace:

twoSum([1, 2, 3, 4, 5], target = 9)

Write the state of seen after each iteration. Identify the exact step where the answer is found. Then answer: could this problem be solved with a Set instead of a Map? If yes, under what modified problem statement would a Set suffice? If no, what information does the Map store that a Set cannot?

Problem 2 — Find the Waste

A developer implements Group Anagrams using a different canonical key — the character sum (sum of ASCII values of all characters):

function groupAnagramsBroken(strs) {
  const groups = new Map();
  for (const s of strs) {
    let key = 0;
    for (const ch of s) key += ch.charCodeAt(0);
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(s);
  }
  return Array.from(groups.values());
}

Part A: Run this on ["eat", "tea", "tan", "ate", "nat", "bat"]. Show the key computed for each string and the resulting groups.

Part B: Find two strings that are NOT anagrams of each other but produce the same key under this hash function. Explain precisely why this canonical key is invalid.

Part C: The sorted-string key is valid but costs O(k log k) per string. Design a canonical key that is O(k) per string and cannot produce false groupings. Justify its correctness: why can two strings produce the same key under your design only if they are anagrams?

Problem 3 — Failure Analysis

A developer tries to solve Longest Consecutive Sequence with sorting:

function longestConsecutiveSorted(nums) {
  if (nums.length === 0) return 0;
  nums.sort((a, b) => a - b);

  let longest = 1;
  let current = 1;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i-1] + 1) {
      current++;
      longest = Math.max(longest, current);
    } else {
      current = 1;
    }
  }

  return longest;
}

Part A: This function has a bug. Find an input where it returns the wrong answer and trace through the execution to show exactly where it goes wrong.

Part B: Fix the bug in the sorted approach with minimal changes. The fix is one line.

Part C: The sorted approach is O(n log n). The Set approach is O(n). For n = 10⁵ elements, estimate the actual operation count difference. At what n does the sorting overhead become significant? At what n would a product engineer (not a competitive programmer) actually prefer the Set approach?

Problem 4 — Design Under Constraints

Design a data structure that implements an LRU (Least Recently Used) cache of capacity k. It must support:

• get(key): Return the value of the key if it exists, otherwise return -1. Mark this key as "recently used."
• put(key, value): Insert or update the key-value pair. If capacity is exceeded, evict the least recently used key first.

Both operations must be O(1).

Why this requires two data structures: O(1) access by key → HashMap. O(1) eviction of the least recently used → need to track order. A regular array/list has O(n) deletion when removing a middle element. You need a data structure that allows O(1) deletion from anywhere.

Your task: Design the LRU Cache using a HashMap combined with a doubly linked list. For each choice:

1. What does the HashMap store as keys? As values?
2. What does the doubly linked list represent — what is the ordering?
3. On get: what nodes move and where?
4. On put: where does the new node go? When capacity is exceeded, which node is evicted?
5. Trace through: put(1,"A"), put(2,"B"), get(1), put(3,"C"), get(2) with capacity=2. Show Map and list state after each operation.

Problem 5 — Reach Beyond

The Contiguous Array problem solved "longest subarray with equal 0s and 1s" using the 0→-1 transformation and prefix sum + HashMap. This technique generalizes.

Part A: "Longest subarray with equal number of 'a' and 'b' characters" — apply the same technique. What is the transformation? What does the running value represent? What do you look up in the Map?

Part B: "Count subarrays where the number of 1s is exactly twice the number of 0s" — this is a harder variant. The condition is count(1s) = 2 × count(0s), i.e., count(1s) - 2×count(0s) = 0. Can you transform the input and apply prefix sum + HashMap? Define the transformation clearly and write the algorithm.

Part C (connection to Chapter 2a): In Chapter 2a, you learned that exactly(K) = atMost(K) - atMost(K-1) can convert exact-count problems into at-most problems, allowing sliding window solutions. The Contiguous Array approach uses a different technique (prefix + HashMap) to handle exact counts directly. When would you prefer the atMost decomposition over the prefix + HashMap approach? Is there any category of problem where one works and the other does not? Construct a concrete example that separates the two — a problem solvable by prefix + HashMap but not by the atMost decomposition, or vice versa.

What's Coming Next

Arrays let you index by position. HashMaps let you index by value. Both are flat — they operate on collections of independent items. But many real problems have structure that is hierarchical or recursive: a problem that contains smaller versions of itself. Sorting a list is done by sorting two halves and merging. Searching a tree means searching one of its subtrees. Computing all subsets means choosing whether to include the current element, then solving the same problem for the remaining elements. Chapter 4 introduces recursion — the ability to express a solution in terms of itself. It is not a data structure. It is a way of thinking that unlocks the next eight chapters.

Sources: Hash Map Patterns for Coding Interviews — AlgoArk; HashMap & HashSet Interview Questions 2025 — GetSDEReady; real interview reports from Zepto, Razorpay, Google India, Amazon India (2024–2026).