Counting with a hash map Explained Step by Step in JavaScript

The idea

Many problems start with the same question: how many times does each value appear? A hash map answers it in one pass. A hash map (a Map in JavaScript) stores pairs of a key and a value, and it can find, add, or change the value for any key in about the same tiny amount of time, no matter how many keys it holds.

To count, use each item as a key and its count as the value. Walk the list once. For each item, read its current count (0 if it isn't in the map yet), add 1, and store it back. When the walk ends, the map knows the count of every distinct item.

With the counts ready, many questions become easy: which item is most common, which appears only once, do two lists hold the same items the same number of times. The code here finds the most frequent item.

An everyday example

Tally marks on a whiteboard

A teacher asks the class to vote for a field trip. Each student calls out a place. The teacher writes each new place on the whiteboard the first time it's called, and adds a tally mark next to it every time it's called again. At the end, one look at the board shows how many votes each place got, and the place with the most marks wins. The teacher never had to go back through the votes a second time.

How the example maps to the code
In the example	In the code
The whiteboard	`counts`, a `Map`
A place called out for the first time	`counts.get(item)` is `undefined`, so `?? 0` treats it as 0
Adding a tally mark	`counts.set(item, count + 1)`
Looking for the place with the most marks	The second loop that tracks `best` and `bestCount`

From the slow way to counting with a hash map

Start with the obvious way to find the most common item: for each item, walk the whole list again and count how many times it appears. With n items that is n walks of n steps each, about n² steps. For 10,000 page views that is 100 million comparisons.
Most of that work is repeated. When the outer loop reaches the second "css", it counts every "css" again, even though it counted them all a moment ago. Each count only needs to be worked out once, if there is somewhere to write it down and find it again quickly.
That place is a table with one row per distinct item. If finding a row meant scanning the table, the code would be slow again. A hash map finds the row for any key in about constant time: it turns the key into a number called a hash and uses that number to jump straight to the row. So one walk over the list can add 1 to the right row for each item.
Once every count is written down, the question "which item is most common?" needs a second, shorter walk over the table instead of over the list. Keep the best count so far and replace it only when a count is strictly bigger. One pass to count and one pass to pick: that loop is counting with a hash map.

How it works

Create an empty Map called counts.
Walk through items. For each item, read counts.get(item) ?? 0, which is 0 the first time.
Store that number plus 1 back with counts.set(item, ...).
After the walk, counts holds every distinct item and how many times it appeared.
To find the most frequent, loop over the map's entries, keeping best and bestCount.
Replace best only when a count is strictly bigger, so on a tie the item seen first wins.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

function mostFrequent(items) {
const counts = new Map();
for (const item of items) {
counts.set(item, (counts.get(item) ?? 0) + 1);
}
let best = null;
let bestCount = 0;
for (const [item, count] of counts) {
if (count > bestCount) {
best = item;
bestCount = count;
}
}
return best;
}

How fast it is

Time	`O(n)`
Extra memory	`O(k)`

Each of the n items costs one get and one set, which take constant time on average. The map stores one entry for each of the k distinct items.

Best caseO(n)
Even the kindest input, like n copies of one item, reads every item once. The second loop is then a single step.
Average caseO(n)
Typical data, such as page names or user ids: each get and set takes about constant time, so the total grows in step with n.
Worst caseO(n)
Every item is distinct, like ["a", "b", "c", "d"]. The map grows to n keys and the second loop also runs n times, about 2n steps in all.

Common mistakes

Writing counts.get(item) + 1 without ?? 0. The first time, get returns undefined, and undefined + 1 is NaN.
Using a plain object, where 1 and "1" become the same key and names like "constructor" already exist.
Counting by calling items.filter(x => x === item).length for every item, which scans the list again each time: O(n^2).
Forgetting the tie rule. Decide whether the first seen, the smallest, or the alphabetically first item wins, and code exactly that.

When to use it

Look for these clues in a problem:

The problem asks "how many times", "most frequent", "appears exactly once", or "at least k times".
Two collections must hold the same items the same number of times (anagrams, matching inventories).
You need to compare counts, such as "can these letters spell that word".
A brute force would count each value by scanning the whole list again, giving O(n^2).

Check yourself

Answer each one in your head first, then open it.

How many times does the second loop run for ["a", "b", "a", "a"]?

Twice, once per distinct item, because it walks counts, not items. The map holds a: 3 and b: 1.

Why does the item seen first win a tie?

A Map gives back entries in the order their keys were first added, and best changes only on a strictly bigger count. So the first entry to reach the top count keeps it.

If every item is distinct, how much memory does counts use?

One entry per item, so O(n). The O(k) bound becomes O(n) when k equals n.

What simpler tool is enough if you only need to know whether any item appears twice?

A Set. You don't need the counts, and you can stop at the first repeat. That is hash set lookup.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 29 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The counting loop keeps one rule: after it has handled some items, each key's value is how many of those items equal that key, and there are no other keys. Before the loop, no items are handled and the map is empty, so the rule holds. A new item changes only its own key, by exactly 1, so the rule still holds after it.

The picking loop has its own rule: after it has looked at some entries, best is the first of those entries with the largest count, and bestCount is that count. A new entry with a strictly bigger count takes over. An entry with an equal count doesn't, because an earlier entry already holds that count. So the rule holds after every entry.

Both rules rely on the Map treating equal items as the same key. A Map compares keys with a rule called SameValueZero: it is like ===, except that NaN matches NaN. So every "css" string lands on one key, while the number 2 and the string "2" stay apart. Both loops end because they walk finite collections, and when the second one ends it has seen every distinct item, so best is the most frequent item, or the first seen of the tied ones.

Going deeper

4 more ideas

Why one pass is enough

After the first loop has handled i items, counts holds the exact count of every value among those i items. Each new item changes exactly one count by exactly 1, so this stays true as the loop moves on. When the loop ends, every count is final.

Why a `Map` and not a plain object

A plain object turns every key into a string, so the number 1 and the string "1" share one count, and keys like "constructor" or "__proto__" can clash with built-in properties. A Map keeps keys exactly as they are and keeps them in the order they were first added, which gives you an easy tie-break: the first item seen comes first.

Counting with a fixed array

When the keys are small whole numbers or lowercase letters, an array of counters is even faster than a Map. For letters, use new Array(26).fill(0) and the index char.charCodeAt(0) - 97. This is the same idea with a cheaper table.

Cost

Each get and set takes O(1) time on average, so counting n items takes O(n) time. The map holds one entry per distinct item, so the extra space is O(k) for k distinct items, at most O(n).

Work it by hand

Every step in a table, with why

Find the most used language in five file types. Two languages tie, so the trace shows how the tie is settled.

items = ["js", "css", "css", "html", "js"]

Step	Loop	`item`	Its count	`best` (`bestCount`)	What happens	Why
1	1st	`"js"`	1	`null` (0)	New key: `?? 0` gives 0, store 1	`counts.get("js")` is `undefined`, so `?? 0` turns it into 0, and `js` is stored with 1.
2	1st	`"css"`	1	`null` (0)	New key: store 1	`css` is added after `js`. The map now holds `js: 1, css: 1`.
3	1st	`"css"`	2	`null` (0)	Seen before: `1 + 1 = 2`	The second `css` finds its row at once and raises it to 2. Nothing is rescanned.
4	1st	`"html"`	1	`null` (0)	New key: store 1	A third distinct key. The map is `js: 1, css: 2, html: 1`.
5	1st	`"js"`	2	`null` (0)	Seen before: `1 + 1 = 2`	`js` keeps its first place in the map's order even though its count changed. A `Map` orders keys by when they were first added.
6	2nd	`"js"`	2	`"js"` (2)	`2 > 0`: new best	The second loop reads the map in first-added order, so `js` comes first. Its 2 beats the starting `bestCount` of 0.
7	2nd	`"css"`	2	`"js"` (2)	`2 > 2` is false: keep `js`	This is the tie. `css` also has 2, but only a strictly bigger count replaces `best`, so the item seen first keeps the lead.
8	2nd	`"html"`	1	`"js"` (2)	`1 > 2` is false	The last entry can't win. The second loop ends after 3 steps, one per distinct item.

It returns "js". Both js and css appear twice, and js wins the tie because it was added to counts first. The first loop ran 5 times, once per item, and the second only 3 times, once per distinct item.

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Counting with a hash map	`O(n)`	`O(n)`	The default: any kind of item, one pass, and the counts answer many follow-up questions.
Fixed-size count array	`O(n)`	`O(1)`	The items are small whole numbers or letters, like 26 lowercase letters. The array's size doesn't grow with `n`, and indexing it is faster than hashing.
Sort, then count runs	`O(n log n)`	`O(1)`	You can't spend extra memory and may reorder the input in place. After sorting, equal items sit next to each other, so one walk counts each run.
Rescan the list for each item	`O(n²)`	`O(1)`	Only for a handful of items, or as the first idea you mention in an interview before improving it.

Extra memory: O(k) for k distinct items, one entry each. That is a fixed size when items come from a small set, like 26 letters, and O(n) when every item is different.

How the steps grow

Counting with a hash map, Fixed-size count array O(n)
Sort, then count runs O(n log n)
Rescan the list for each item O(n²)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Counting with a hash map	10	1,000	1 million
Fixed-size count array	10	1,000	1 million
Sort, then count runs	33	9,966	20 million
Rescan the list for each item	100	1 million	1 trillion

Inputs that need care

6 tricky inputs

An empty list: items = []: Neither loop runs, so best stays null and the function returns null. Callers must check for null before using the answer.
One item: items = ["x"]: counts becomes x: 1, the second loop runs once, and "x" is returned.
A tie: ["b", "a", "a", "b"]: Both have 2. b was added to the map first, so "b" is returned. If the problem wants the alphabetically first item on a tie, change the test to count > bestCount || (count === bestCount && item < best).
Mixed types: [1, "1", 1]: A Map keeps the number 1 and the string "1" as different keys, so 1 wins with 2. A plain object would merge them into one key with count 3.
NaN values: [NaN, NaN, 4]: A Map treats NaN as equal to itself, so NaN gets count 2 and is returned, even though NaN === NaN is false.
Objects as items: two separate { id: 1 } objects: They are two keys, because a Map compares objects by identity. To count them as one, use a field as the key, such as item.id.

Variations and follow-ups

Twists interviewers add

The `k` most frequent items

Count first, then make an array of buckets where buckets[c] lists the items with count c. Read the buckets from the highest count down until you have k items. Counts can't be bigger than n, so this is O(n) with no sorting.

Comparing two collections

To check whether two lists hold the same items the same number of times, count up for the first list and count down for the second, in one map. If every count ends at 0, they match. This is how you check that two words use the same letters.

The first item that appears once

Count everything, then walk the original list again, not the map, and return the first item whose count is 1. Walking the list keeps the list's order, which is what "first" means here.

Counts inside a moving window

For "most common value among the last 50 events", add 1 for the event entering the window and subtract 1 for the event leaving it. Delete a key when its count reaches 0, so the map's size stays the number of distinct items in the window.

In an interview

Spot it, explain it, answer follow-ups

Spot it from words like "most frequent", "appears exactly once", "at least k times", "same letters", or any comparison of two collections that ignores order.
Say the two phases out loud: "one pass builds counts, and a second pass over the map answers the question." Then state your tie rule before you code it.
Test three small inputs by hand: an empty list, one item, and a tie. The tie is where an answer most often differs from what the problem wants.
The usual follow-up is "return the k most frequent items". Answer with buckets indexed by count, which is O(n), or a min-heap of size k, which is O(n log k) and works when k is small.
If asked "what if the data doesn't fit in memory?", say that exact counts for every item need memory for every item. Then mention the Boyer-Moore vote when only a majority matters, or approximate counters when small errors are fine.

Where frontend code uses it

The same idea in real UI code

Counting analytics events by name ("click", "scroll", "purchase") before sending a summary from the browser.
Finding duplicate key values in a list before rendering it in React, which would otherwise cause a console warning and confused updates.
Building a tag cloud or a filter sidebar that shows how many products have each brand or color.
Checking whether two strings use the same letters, for example in a word game or a search box that ignores letter order.

Counting with a hash map

The idea

An everyday example

Tally marks on a whiteboard

From the slow way to counting with a hash map

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why one pass is enough

Why a `Map` and not a plain object

Counting with a fixed array

Cost

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

The `k` most frequent items

Comparing two collections

The first item that appears once

Counts inside a moving window

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Tally marks on a whiteboard

From the slow way to counting with a hash map

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why one pass is enough

Why a Map and not a plain object

Counting with a fixed array

Cost

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

The k most frequent items

Comparing two collections

The first item that appears once

Counts inside a moving window

In an interview

Where frontend code uses it

Related algorithms

Why a `Map` and not a plain object

The `k` most frequent items