Day 6: Hash Maps & Sets

DAY 6 / 30 · WEEK 1

Goal of the day

• Use Map and Set fluently for average O(1) lookup, insert, and delete.
• Recognize the frequency-counting pattern: “have I seen this?” / “how many times does X appear?”
• Turn an O(n²) nested-loop search into O(n) by trading space for time.

Concept

A hash map is like a coat check counter with numbered tickets. Without it, finding your coat means checking every coat on the rack one by one — O(n). With a ticket number, the attendant jumps straight to your coat — O(1) on average. A hash map does this by running each key through a hash function that turns it into a number, then uses that number to jump directly to a storage slot, instead of scanning.

This is the biggest lever you’ll pull all month: almost any “have I seen this before?” or “how many times does X appear?” question can go from an O(n²) nested loop (checking every element against every other element) to a single O(n) pass, by remembering what you’ve seen in a Map or Set as you go — at the cost of O(n) extra memory. That trade — memory for speed — is the single most common move in interview solutions.

Diagrams

1. Linear scan vs. hash lookup

2. Frequency counting

Interactive visualizations

1. Two Sum with a hash map

Running example: nums = [3, 2, 4], target = 6

Press Play or Step to begin.

map entries: 0

Step 0 / 4

▶ Play⏭ Step↺ Reset🔀 Shuffle

2. First unique character

Running example: s = "swiss"

Press Play or Step to begin.

pass: 1 · character: —

Step 0 / 3

▶ Play⏭ Step↺ Reset🔀 Shuffle

The code

// --- Two Sum, the O(n) way (Day 2 showed the O(n²) brute force) ---
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);
  }
  return [-1, -1];
}

// --- Frequency counting ---
function firstUniqChar(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  for (let i = 0; i < s.length; i++) {
    if (counts.get(s[i]) === 1) return i;
  }
  return -1;
}

Line by line:

• twoSum — for each number, first check whether its complement (what it would need to reach the target) is already in the map. Only if not, add the current number. This single pass replaces the nested loop entirely — no sorting needed, unlike Day 4’s two-pointer version.
• firstUniqChar — two passes, both O(n): the first builds a full frequency count; the second finds the first character whose count is exactly 1. You can’t combine these into one pass, because a character’s final count isn’t known until the whole string has been scanned.

Dry run: twoSum([3, 2, 4], target = 6)

i	nums[i]	complement	In map?	Action
0	3	3	No	seen.set(3, 0) → {3: 0}
1	2	4	No	seen.set(2, 1) → {3: 0, 2: 1}
2	4	2	Yes (index 1)	return [1, 2]

Found in one pass, no sorting, works even though the array isn’t sorted — the exact case Day 4’s two-pointer version couldn’t handle directly.

Complexity

Operation	Time	Space	Why
map.get / set / has	O(1) average, O(n) worst case	O(1) per call	Worst case: every key collides into the same slot, degrading to a linear scan.
Two Sum, brute force (Day 2)	O(n²)	O(1)	Check every pair.
Two Sum, hash map (today)	O(n)	O(n)	One entry per number seen so far — genuinely unbounded, since numbers can be arbitrary.
Frequency counting a string/array	O(n)	O(min(n, alphabet size))	One count per distinct element. For a fixed small alphabet (e.g. lowercase English letters, 26 possible keys) this is really O(1) space, not O(n) — it only grows with n when the value range itself is unbounded.

Interview corner

• Map vs. a plain object — when do you use which? Prefer Map by default: any value can be a key (not just strings), it preserves insertion order reliably, has a real .size, and has no prototype to accidentally collide with (a key literally named "toString" is safe in a Map, not in a plain object).

• Why is hash lookup “O(1) average” instead of just “O(1)”? Different keys can hash to the same slot (a collision). A well-implemented hash map handles this gracefully and stays close to O(1) in practice, but a pathological set of keys can degrade it toward O(n).

  • ↳ Common follow-up: “How would you handle collisions yourself?” — chaining (each slot holds a small list) or open addressing (probe for the next free slot) are the two classic answers.

• What’s the classic trap with frequency-counting problems? Trying to do it in one pass when the answer genuinely depends on the final count of something (like “first unique character”) — you can’t know a character is unique until you’ve seen the whole string.

  • ⚠ Trap: don’t fight this — two clean O(n) passes is still O(n) overall, and far less buggy than a contorted attempt at one pass.

How to talk through it out loud: name the trade explicitly — “I’ll use a hash map to remember what I’ve seen, which costs O(n) extra space but drops the time from O(n²) to O(n).” Interviewers want to hear that you know it’s a trade, not a free win — mentioning the space cost unprompted is a strong signal.

Practice problems

1. Two Sum

Easy — LeetCode: Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target. (You wrote the O(n²) brute force for this on Day 2 — now write the O(n) version.)

Show hint

For each number, ask “have I already seen the number that would complete this pair?” before adding the current number to the map.

Show solution

function twoSum(nums, target) {
  const seen = new Map();
  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);
  }
  return [-1, -1];
}

2. Valid Anagram

Easy — LeetCode: Valid Anagram

Given two strings, return true if the second is an anagram of the first (same letters, same counts, any order).

Show hint

Build a frequency count of the first string, then walk the second string subtracting from those counts. If anything goes negative, or the lengths differ, they’re not anagrams.

Show solution

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);
  for (const ch of t) {
    if (!counts.get(ch)) return false; // missing, or already at 0
    counts.set(ch, counts.get(ch) - 1);
  }
  return true;
}

3. Group Anagrams

Medium — LeetCode: Group Anagrams

Given an array of strings, group the anagrams together (any order).

Show hint

Anagrams share the same sorted letters. Use that sorted string as a map key, and group original words under it.

Show solution

function groupAnagrams(strs) {
  const groups = new Map();
  for (const word of strs) {
    const key = word.split('').sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

Quiz

1. What’s the average time complexity of map.get(key)?

Choose one

• O(1) — correct!
• O(n)
• O(log n)

Map.get/set/has are O(1) on average — that’s the entire point of a hash map.

2. Why can hash map lookups degrade to O(n) in the worst case?

Choose one

• Hash collisions — multiple keys landing in the same slot — correct!
• The map has to stay sorted
• Garbage collection pauses

When many keys hash into the same slot, the map has to fall back to scanning within that slot — the worst case degrades toward O(n).

3. For general-purpose key/value storage in an interview solution, which is the safer default?

Choose one

• Map — correct!
• A plain object ({})
• They’re equally safe in every case

Map accepts any key type, preserves insertion order reliably, and has no prototype to accidentally collide with.

4. In the hash-map Two Sum, what does the map store as each value’s mapped data?

Choose one

• The index where that value was seen — correct!
• How many times that value appeared
• The target sum

Storing value -> index lets you instantly return the position of a previously-seen number once its complement shows up.

5. The frequency-counting pattern is the right fit for problems like:

Choose one

• Counting occurrences, detecting duplicates, comparing anagrams — correct!
• Sorting an array into ascending order
• Computing a recursive tree traversal

Detecting duplicates, counting occurrences, and comparing anagrams are all classic ‘remember what you’ve seen’ problems — exactly what frequency counting solves.