Algorithms from zero

Frequency counting

Crux Count how many times each value appears using a hash map: one O(n) pass builds a frequency tally. Solve anagrams, find duplicates, and group by count.

◷ 18 min

You have a string “mississippi” and you want to know: how many times does each letter appear? One approach: for each letter, scan the string and count. That is O(n²) — n letters, each requiring a scan. But here is the key insight: traverse the string once, and as you go, tally each letter in a hash map. When you reach the end, your hash map contains the full frequency count. One pass, O(n) time. This is the frequency counting pattern, and it is the most common use of hash maps.

Goal

After this lesson you can build a frequency map in one O(n) pass, use a frequency map to solve “is this an anagram?”, find the most common element in an array, detect non-repeating elements, understand why a fixed-size alphabet allows an array-based frequency table, and recognize that frequency counting replaces the O(n²) “scan and count for each element” approach.

The idea

The problem we are solving:

You are asked: count how many times each letter appears in “hello”. One method:

function countNaive(str) {
  // For each letter, scan the string and count
  for (let i = 0; i < str.length; i++) {
    let count = 0;
    for (let j = 0; j < str.length; j++) {
      if (str[i] === str[j]) count++;
    }
    console.log(str[i] + ": " + count);  // h: 1, e: 1, l: 2, l: 2, o: 1
  }
}

This is O(n²): for each of n letters, you scan the entire string. For large inputs, this is wasteful.

The frequency counting idea:

Instead, traverse the string once. For each letter you encounter, update its count in a hash map:

function countFreq(str) {
  const freq = new Map();  // frequency map: letter → count
  
  for (let char of str) {
    // Increment the count for this character
    freq.set(char, (freq.get(char) ?? 0) + 1);
  }
  
  // freq now contains: h→1, e→1, l→2, o→1
  return freq;
}

One loop, O(n) time. One hash map, O(k) space where k is the number of distinct letters.

Why it works:

First pass: traverse each element once. Add to map if new, increment if seen before.
O(1) updates: freq.set() and freq.get() are O(1) on average.
Result: after one pass, the map is complete.

Hash map vs. array for small alphabets:

If the keys are a small fixed range (e.g., lowercase letters a–z), you can use a plain array instead of a hash map:

function countFreqArray(str) {
  const freq = new Array(26).fill(0);  // 26 slots for a-z
  
  for (let char of str) {
    const index = char.charCodeAt(0) - 'a'.charCodeAt(0);  // 'a'→0, 'b'→1, etc.
    freq[index]++;
  }
  
  // freq[0] is count of 'a', freq[1] is count of 'b', etc.
  return freq;
}

Array access is O(1) and slightly faster than hash map operations (no hashing overhead). Both work; the array is optimized when the keys are small and predictable.

Common uses of frequency maps:

Anagrams: two strings are anagrams if they have the same character frequencies.
Duplicates and non-repeating: find elements that appear exactly once or more than once.
Most/least common: track the element with the highest or lowest count.
Group by count: organize elements by frequency.

The code

1. Building a frequency map:

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

const counts = frequency([5, 2, 5, 9, 5, 3, 2]);
// counts: 5→3, 2→2, 9→1, 3→1
console.log(counts.get(5));  // 3

2. Checking if two strings are anagrams:

Two strings are anagrams if they contain the same characters with the same frequencies.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  
  const freq = new Map();
  
  // Count characters in s
  for (let char of s) {
    freq.set(char, (freq.get(char) ?? 0) + 1);
  }
  
  // Decrement for characters in t
  for (let char of t) {
    if (!freq.has(char)) return false;
    freq.set(char, freq.get(char) - 1);
    if (freq.get(char) < 0) return false;
  }
  
  // All counts should be 0
  for (let count of freq.values()) {
    if (count !== 0) return false;
  }
  
  return true;
}

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

3. Finding the first non-repeating character:

function firstNonRepeating(str) {
  const freq = new Map();
  
  // Count all characters
  for (let char of str) {
    freq.set(char, (freq.get(char) ?? 0) + 1);
  }
  
  // Find the first character with count 1
  for (let char of str) {
    if (freq.get(char) === 1) {
      return char;
    }
  }
  
  return null;  // No non-repeating character
}

console.log(firstNonRepeating("abacabad"));  // 'c'
console.log(firstNonRepeating("aabbcc"));    // null

Try the examples:

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

const counts = frequency([5, 2, 5, 9, 5, 3, 2]);
console.log("Frequency of [5,2,5,9,5,3,2]:");
console.log("  5 appears", counts.get(5), "times");
console.log("  2 appears", counts.get(2), "times");

console.log("\nAnagrams:");
console.log("  'listen' and 'silent':", isAnagram("listen", "silent"));
console.log("  'hello' and 'world':", isAnagram("hello", "world"));

console.log("\nFirst non-repeating:");
console.log("  'abacabad':", firstNonRepeating("abacabad"));
console.log("  'aabbcc':", firstNonRepeating("aabbcc"));

Output

Step-by-step trace

Let us trace building a frequency map on the string “aabab”:


      1
      function frequency(str) {
    

      2
        const freq = new Map();
    

      3
        for (let char of str) {
    

      4
          freq.set(char, (freq.get(char) ?? 0) + 1);
    

      5
        }
    

      6
        return freq;
    

      7
      }

Notice: we visited each character exactly once. Each set and get is O(1). Total time: O(n).

Complexity

Frequency counting:

Operation	Time	Space
Build frequency map	O(n)	O(k)
Check if anagram	O(n)	O(k)
Find first non-repeating	O(n)	O(k)
Find most common element	O(n)	O(k)

Where n is the size of the input (string length or array size) and k is the number of distinct values.

Comparison: naive O(n²) vs. frequency counting O(n):

Naive approach: for each element, scan the entire input to count it. n × n = O(n²).
Frequency counting: one pass to build the map, then use the map. O(n) + O(n) = O(n).

For n = 1000, naive is 1,000,000 operations. Frequency counting is 2,000. The difference grows fast.

Space for the array-based variant:

If the alphabet is fixed (e.g., lowercase letters, 26 values), the space is O(26) = O(1) constant. The frequency counting time is still O(n), but space is O(1) instead of O(k).

Practice 0 / 5

Why does frequency counting count each element's occurrences in O(n) time instead of O(n²)?

Two strings are anagrams if they contain the same characters with the same frequencies. Which approach is more efficient?

In a string of length 100 with 8 distinct characters, how much space does a frequency map use?

When counting character frequencies in a string of lowercase letters only (a–z), which data structure is fastest?

To find the first non-repeating character in a string, do you need to build the frequency map first, or can you check while building?

lesson.inset.misconception

“Frequency counting is only for strings.” Not true. Frequency counting works on any array of comparable values: integers, objects (if hashable), pairs, etc. The pattern is the same: one pass, count in a hash map, use the result.

Edge cases

Empty or single-character input: An empty string has no characters, so the frequency map is empty. A single-character string has one entry: the character with count 1. Always test edge cases.

Check yourself

Quiz

Why is the frequency counting pattern O(n) time, even though you might think 'I have to count each element' sounds like O(n²)?

Recap

Frequency counting is the practice of counting how many times each value appears in a dataset using a hash map.

Key facts:

One-pass algorithm: traverse the input once. For each element, increment its count in the map using map.set(key, (map.get(key) ?? 0) + 1).
Time complexity: O(n), where n is the size of the input.
Space complexity: O(k), where k is the number of distinct values.
Common uses:
- Check if two strings are anagrams (same character frequencies).
- Find the first non-repeating element.
- Detect elements that appear exactly once or more than once.
- Find the most or least common element.
Array optimization: if the keys are a small fixed range (e.g., lowercase letters a–z), use an array instead of a hash map for O(1) space and slightly faster operations.
Replaces O(n²): the naive approach of scanning for each element is O(n²). Frequency counting solves the same problem in O(n).

You now have the most common hash map pattern. Next, you will explore collision handling and learn how hash functions distribute keys.

Continue the climb ↑The ''''seen'''' pattern