Frequency Counting

Master the frequency-map pattern: count characters or elements in one pass, then answer questions about the data in O(1) lookups.

5 min read Level 2/5 #dsa#hashing#frequency-counting

What you'll learn

Build a character-frequency map from a string in O(n)
Use frequency maps to detect anagrams without sorting
Extract the top-k most frequent elements from a frequency map

The frequency-counting pattern converts an array or string into a Map of value-to-count in a single O(n) pass. Once the map exists, you can answer most “how many times does X appear?” questions in O(1). This eliminates the need for nested loops and drops many O(n²) brute-force solutions to O(n).

Building a Frequency Map

function frequencyMap(arr) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) ?? 0) + 1);
  }
  return freq;
}

const words = ["apple", "banana", "apple", "cherry", "banana", "apple"];
const freq = frequencyMap(words);

console.log(freq.get("apple"));  // 3
console.log(freq.get("banana")); // 2
console.log(freq.get("date"));   // undefined

The ?? 0 handles the first occurrence: get returns undefined, and undefined ?? 0 gives 0, so the count starts at 1.

Character Frequencies

The same pattern works on strings. Iterating with for...of gives each Unicode character correctly, even for multi-byte characters:

function charFreq(str) {
  const freq = new Map();
  for (const ch of str) {
    freq.set(ch, (freq.get(ch) ?? 0) + 1);
  }
  return freq;
}

const f = charFreq("mississippi");
console.log(f.get("s")); // 4
console.log(f.get("i")); // 4
console.log(f.get("p")); // 2

Anagram Check Preview

Two strings are anagrams if their character frequency maps are identical. You can check this by building one map and decrementing for the second string:

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const freq = new Map();
  for (const ch of a) freq.set(ch, (freq.get(ch) ?? 0) + 1);
  for (const ch of b) {
    if (!freq.has(ch)) return false;
    const count = freq.get(ch) - 1;
    if (count === 0) freq.delete(ch);
    else freq.set(ch, count);
  }
  return freq.size === 0;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("hello",  "world"));  // false

The full group-anagrams problem is covered in the next lesson.

Top-K Most Frequent Elements

Sort the frequency map entries by count descending and slice the first k:

function topK(arr, k) {
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) ?? 0) + 1);
  }
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([item]) => item);
}

const nums = [1, 1, 1, 2, 2, 3];
console.log(topK(nums, 2)); // [1, 2]

Sorting takes O(n log n). For a true O(n) solution you would use bucket sort on the frequencies — a technique covered in the sorting track.

Complexity Summary

Step	Time	Space
Build frequency map	O(n)	O(k)
Single lookup	O(1)	—
Top-k (sort approach)	O(n log n)	O(n)

k is the number of distinct values (at most n).

Up Next

Apply frequency counting to the classic group-anagrams problem and see two different key strategies with Map.

Anagrams →