Hash maps: remember what you've seen

Instead of searching the array again and again, walk it once and write down what you need in a Map or Set. Then every "have I seen this?" or "how many so far?" question takes one step.

Think of it like this: a coat check. You hand over your coat and get a ticket. Later the attendant goes straight to that ticket number. They don't look through every coat on the rail.

Why it matters

Three jobs a map does

How to spot it

Words and constraints in a problem that point to this pattern:

• “Find two numbers that add up to…”, or any “does a matching item exist?” question
• Counting: “how many times”, “most frequent”, “appears exactly once”, “same letters in a different order”
• “Duplicate”, “seen before”, “unique”, “first to repeat”
• “Group the items that share…”
• Your first idea is a nested loop where the inner loop searches for one specific value

Watch it work

The template

// Shape 1: "seen before": one pass, check, then remember
function seenBefore(items: number[]): boolean {
  const seen = new Set<number>();          // values we've already passed
  for (const x of items) {                 // visit each item once
    const wanted = /* the value that would complete the answer for x */ x;
    if (seen.has(wanted)) {                // O(1) question instead of an inner loop
      return true;                         // or build the answer you need here
    }
    seen.add(x);                           // remember x AFTER the check
  }
  return false;                            // walked everything, no match
}

// Shape 2: "count": build a frequency map, then read it
function countThings(items: string[]): Map<string, number> {
  const counts = new Map<string, number>(); // key: the item, value: how many times
  for (const x of items) {
    counts.set(x, (counts.get(x) ?? 0) + 1); // missing key counts as 0
  }
  return counts;                           // second pass reads these counts
}

Worked example

1. Start with the direct idea: for each character, scan the whole string and count how many times it appears. Return the first one whose count is 1. That's a loop inside a loop: O(n²).

   for (let i = 0; i < s.length; i++) {
     let count = 0;
     for (let j = 0; j < s.length; j++) {
       if (s[j] === s[i]) count++;
     }
     if (count === 1) return i;
   }
   return -1;
   

2. Spot the waste. In "swiss", the inner loop counts the letter s three separate times, once for each s. The counts never change, so we're redoing the same work.

3. Pick the job: this is counting. Key: the character. Value: how many times it appears. Build the counts in one pass first.

4. Then make a second pass over the string, in order, and return the first index whose count is 1. Order matters here: we loop over the string, not the Map, so "first" means first in the string. Two separate loops: O(n) + O(n) = O(n).

   function firstUniqueIndex(s: string): number {
     const counts = new Map<string, number>();
     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;
   }
   

5. Check the edge cases. "aabb": every count is 2, the second loop finds nothing, return -1. "": both loops do nothing, return -1. "z": count of z is 1, return 0.

Common mistakes

• Storing before checking in a "seen before" loop, so every item matches itself. For example, the first element gets reported as a duplicate.
• Writing counts.set(x, counts.get(x) + 1) without ?? 0. The first time, undefined + 1 is NaN, and every count becomes NaN.
• Checking if (map.get(k)) when the stored value can be 0, such as an index or a count. 0 is falsy, so a real entry looks missing. Use map.has(k).
• Looping over the Map to find "the first" in the original order when the order you need is the input's. Loop over the input for the second pass.
• Using an array as a key (map.set([1, 2], …)). Arrays compare by reference, so map.get([1, 2]) is undefined. Build a string key such as "1,2".

Cost

In interviews