Linear-Time Frequency Counting

In our previous lesson, we saw how a Set can efficiently track whether an element has been seen before, reducing an $O(n^2)$ problem to $O(n)$. Today, we'll build on that foundation. What if simply knowing if we've seen something isn't enough? What if we need to know how many times we've seen it? This brings us to the frequency counting pattern.

This lesson will teach you how to apply frequency counting to solve lookup and comparison problems in linear time. We will move from the binary "seen/unseen" logic of a Set to the quantitative counting power of a Map. This pattern is a workhorse in algorithm interviews, enabling elegant and efficient solutions to a whole class of problems that involve comparing the composition of data sets.

From Existence to Frequency

The "seen set" pattern answers the question: "Does this item exist in my collection?" Frequency counting answers a more detailed question: "How many of this item exist in my collection?"

The ideal tool for this job in JavaScript/TypeScript is the Map data structure (or a plain Object), which allows us to associate a key (the element we're counting) with a value (its frequency). Because Map provides average-time $O(1)$ for getting and setting values, we can build a complete frequency profile of a collection in a single, linear pass.

The infographic below provides a fantastic high-level overview of this concept, which is often called the Frequency Map pattern.

As you can see, this simple idea of counting things is powerful. It allows us to transform problems that seem to require expensive comparisons or sorting into simple arithmetic operations on counts, often leading to a significant time complexity improvement.

The Core Pattern: Building a Frequency Map

Let's start by looking at the fundamental implementation. The goal is to iterate through a collection (like an array or a string) and build a Map that stores each unique element and its corresponding count.

Here's the standard, idiomatic way to do this in TypeScript:

function buildFrequencyMap(items: string[] | number[]): Map<string | number, number> {
    const frequencyMap = new Map<string | number, number>();

    for (const item of items) {
        // Get the current count, defaulting to 0 if the item isn't in the map yet.
        const currentCount = frequencyMap.get(item) ?? 0;
        // Increment the count and update the map.
        frequencyMap.set(item, currentCount + 1);
    }

    return frequencyMap;
}

// Example usage:
const nums = [1, 2, 2, 3, 3, 3];
const freqMap = buildFrequencyMap(nums);
console.log(freqMap); // Map(3) { 1 => 1, 2 => 2, 3 => 3 }

The key line here is frequencyMap.set(item, (frequencyMap.get(item) ?? 0) + 1). As an experienced developer, you'll recognize the nullish coalescing operator (??) as a clean way to handle the initial case where an element is not yet in the map. This single line encapsulates the logic of "get the count, add one, and put it back," which is the heart of the frequency counting loop.

The following reading provides a great summary of this pattern, its variations, and, importantly, the signals that tell you when to use it.

Application: Valid Anagram

A classic problem that perfectly illustrates frequency counting is "Valid Anagram" (LeetCode 242).

Given two strings, s and t, return true if t is an anagram of s, and false otherwise.

An anagram is a word formed by rearranging the letters of another, using all original letters exactly once. For example, "anagram" and "nagaram" are anagrams.

How can we determine this? The definition itself gives us the answer: they must have the exact same character frequencies. "cinema" and "iceman" are anagrams because both have one 'c', one 'i', one 'n', one 'e', one 'm', and one 'a'.

A common approach that doesn't use frequency counting is to sort both strings and check if they are equal.

• s = "anagram" -> sort -> "aaagmnr"
• t = "nagaram" -> sort -> "aaagmnr"
  They are equal, so it's a valid anagram. This works, but sorting takes $O(L\log L)$ time, where $L$ is the length of the string. We can do better.

Using a frequency map, we can solve this in $O(L)$ time. There are two main ways:

1. Two Maps: Build a frequency map for s and another for t. Then, compare the two maps to ensure they are identical.
2. Increment/Decrement (One Map): This is a more space-efficient and often faster variant.
   • First, perform a quick check: if the strings have different lengths, they can't be anagrams, so return false.
   • Build a frequency map for the first string, s.
   • Iterate through the second string, t. For each character in t, decrement its count in the map.
   • During the decrement step, if a character from t is not found in the map, or if its count is already 0, it means t has a character that s doesn't (or has too many of one character). Return false.
   • If the loop completes without any issues, it means every character in t was successfully "cancelled out" from the frequency map of s, so they are anagrams.

The following video provides an excellent walkthrough of this one-map strategy in JavaScript.

The complexity of this approach is:

• Time Complexity: $O(L)$, where $L$ is the length of the strings. We iterate through s once to build the map and through t once to check it.
• Space Complexity: $O(k)$, where $k$ is the number of unique characters. In the case of lowercase English letters, $k$ is at most 26. Since this doesn't depend on the input size $L$, we can consider it $O(1)$ constant space.

A Glimpse at a More Complex Application

The frequency counting pattern isn't just for simple one-to-one comparisons. It can also be used to create a "fingerprint" or a canonical key to group items. Consider the "Group Anagrams" problem (LeetCode 49), where you are given a list of strings and must group the anagrams together.

For ["eat", "tea", "tan", "ate", "nat", "bat"], the output should be [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]].

How can we solve this? We can iterate through each string, generate a frequency-based fingerprint for it, and use that fingerprint as a key in a map. The value associated with that key would be a list of all strings that share that fingerprint.

For example, "eat", "tea", and "ate" all share the same fingerprint: one 'a', one 'e', one 't'. We could represent this fingerprint as a sorted string ("aet") or a count array/string (e.g., "1a0b0c...1e...1t..."). Then, our map would look like this:
{ "aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"] }

The video below explains this elegant solution. You don't need to master this just yet, but seeing it will help solidify your understanding of how versatile frequency counting can be.

Conclusion

In this lesson, we leveled up from checking for existence with a Set to counting occurrences with a Map. This seemingly small step unlocks a powerful algorithmic pattern.

Key Takeaways:

• Frequency Counting is used when a problem's solution depends on the number of times elements appear, not their order.
• The primary tool is a Map (or hash map), which provides $O(1)$ average time complexity for lookups and updates.
• This pattern can often reduce time complexity from $O(n\log n)$ (for sorting-based solutions) or $O(n^2)$ (for nested-loop comparisons) to $O(n)$, at the cost of $O(k)$ space for the map (where k is the number of unique items).
• Common signals for this pattern include problem descriptions mentioning "anagrams," "permutations," "same elements," or direct questions about "frequency" or "occurrences."

In our next lesson, we will explore another powerful use of hash maps: solving "complement-lookup" problems. Instead of mapping an element to its frequency, we will map an element to its position (index). This will enable us to answer questions like, "For a given number x, have we already seen the number target - x?" This is the key to solving the famous "Two Sum" problem in linear time.