DAY 6 / 30 · WEEK 1

Hash Maps & Sets

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

2. First unique character

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)

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

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

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];
}

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;
}

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