Skip to content
Hash map: count and look up

Lesson 4.1

Count frequencies

6 min · 7 steps

  1. Step 1 of 7 · Explanation

    A Map stores key and value pairs, and it can find a key in one step. For counting, the key is the item and the value is how many times it has appeared.

    You'll use this one line all the time: counts.set(x, (counts.get(x) || 0) + 1). If x isn't there yet, get gives undefined, and || 0 turns it into 0.

  2. Step 2 of 7 · Predict the result

    This function returns the highest count. What does it return for "mississippi"?

    function solution(s) {  const counts = new Map()  let best = 0  for (const ch of s) {    const c = (counts.get(ch) || 0) + 1    counts.set(ch, c)    if (c > best) best = c  }  return best}
    1. 4
    2. 8
    3. 11
    4. 2

  3. Step 3 of 7 · Find the bug

    For "aab", this code returns NaN, but it should be 2. Tap the wrong line.

    function solution(s) {  const counts = new Map()  for (const ch of s) {    counts.set(ch, counts.get(ch) + 1)  }  return counts.get("a")}

  4. Step 4 of 7 · Trace the code

    Fill in x and c at the marked steps. c is the new count for x.

    function solution(nums) {  const counts = new Map()  let maxCount = 0  for (const x of nums) {    const c = (counts.get(x) || 0) + 1    counts.set(x, c)    maxCount = Math.max(maxCount, c)  }  return maxCount}

    solution([2, 7, 2, 2])

  5. Step 5 of 7 · Arrange the code

    Build a function that returns the first letter that appears exactly once, or "" if there is none. Count first, then search. Two lines don't belong.

    if (counts.get(ch) > 1) return ch}const counts = new Map()if (counts.get(ch) === 1) return ch}for (const ch of s) {for (const ch of s) {}return ""counts.set(ch, 1)function solution(s) {counts.set(ch, (counts.get(ch) || 0) + 1)

  6. Step 6 of 7 · Pick the approach

    "Return the name that appears most often in votes." Constraints: 1 ≤ votes.length ≤ 10⁵.
    Which approach fits best?

    1. A Map from name to count, in one pass
    2. For each name, count its appearances with an inner loop
    3. Sort first, then count runs of equal names
    4. A plain array indexed by name

  7. Step 7 of 7 · Recap

    • A Map finds a key in one step. For counting, the key is the item and the value is its count.
    • counts.get(x) for a new key is undefined. Always add || 0.
    • Many problems need two passes. First count, then use the counts.

    Pattern card

    Count with a Map
    When to use it: When a problem asks "how many times", "most often", "appears once", or "same number of".
    const counts = new Map()for (const x of items) {  counts.set(x, (counts.get(x) || 0) + 1)}