Frequency counting is a technique where we count the occurrences of elements (characters, numbers, or any objects) and use these counts to solve problems. The core data structures are hash maps and fixed-size arrays.

A hash map (or dictionary) stores counts for arbitrary elements with O(1) average lookup and update time. A fixed-size array works when the element range is known and small, like the 26 lowercase English letters.

The power of frequency counting comes from reducing complex comparisons to simple count comparisons. Two strings are anagrams if and only if they have identical character frequencies. An array has duplicates if any element has a frequency greater than one.

Why Frequency Counting Works

Many problems that seem to require expensive operations can be solved by counting:

Anagram Detection: Instead of generating all permutations of a string (O(n!) operations), we count character frequencies in O(n) time and compare counts in O(1) time (for fixed alphabet).

Duplicate Finding: Instead of comparing every pair of elements (O(n^2)), we count occurrences and check if any count exceeds one.

Matching Problems: Instead of sorting both collections to compare (O(n log n)), we count elements in each and compare frequency maps in O(n) time.

The key insight is that order does not matter for many problems. When order is irrelevant, frequency counting captures all the information we need.

When to Use Frequency Counting

Frequency counting is the right tool when you see these patterns:

1. The problem mentions "anagram" or "permutation"

Anagrams are strings with the same character frequencies. Permutations are sequences with the same element frequencies.

2. The problem asks about "duplicates" or "unique elements"

Finding duplicates means finding elements with frequency > 1. Finding unique elements means finding elements with frequency = 1.

3. The problem involves comparing composition, not order

If you need to check whether two collections have "the same elements" regardless of order, frequency counting is your tool.

4. The problem asks about "occurrence count" or "frequency"

Any problem explicitly asking how many times something appears is a direct frequency counting problem.

5. The problem involves matching or grouping by content

Grouping anagrams together, finding words that use the same letters, or matching patterns all use frequency counting.

Here are common problem types where frequency counting excels:

Frequency Counting Variants

There are several patterns within frequency counting, each suited for different problem types.

Variant 1: Single Frequency Map

Count occurrences of elements in a single collection.

Use this when: finding duplicates, counting occurrences, finding the most/least frequent element.

Variant 2: Two Frequency Maps Comparison

Build frequency maps for two collections and compare them.

Use this when: comparing composition of two collections, checking if they are anagrams/permutations.

Variant 3: Increment/Decrement Pattern

Use a single map with increment for one collection and decrement for another. If the map is empty (or all zeros) at the end, the collections match.

Use this when: comparing two collections with memory efficiency, or when processing in a streaming fashion.

Variant 4: Fixed-Size Array

When the element domain is known and small (like lowercase letters), use an array instead of a hash map for better performance.

Use this when: working with lowercase letters (26 slots), uppercase letters (26 slots), ASCII characters (128 slots), or digits (10 slots).

Basic Frequency Counting Template

Here is the most general template for frequency counting with a hash map:

For strings with lowercase letters, the array-based template is more efficient:

For comparing two strings as anagrams:

Example Walkthrough: Count Word Frequency

Let us work through a complete example. Given a sentence, count the frequency of each word.

Problem: Given a string sentence, return a map of each word to its frequency.

Solution

Detailed Walkthrough

Time Complexity: O(n) where n is the number of characters (or O(w) where w is the number of words)

Space Complexity: O(k) where k is the number of unique words

Example Walkthrough: Find Duplicate in Array

Problem: Given an array of integers, return true if any value appears more than once.

Solution

Alternatively, using a frequency map:

Detailed Walkthrough

Time Complexity: O(n) - we process each element once

Space Complexity: O(n) - in the worst case, we store all elements

Pattern Used: Set for existence checking (simplified frequency counting where we only care about count > 0)

Example Walkthrough: Check If Two Arrays Have Same Elements

Problem: Given two arrays, determine if they contain the same elements with the same frequencies (i.e., one is a permutation of the other).

Solution

Detailed Walkthrough

Time Complexity: O(n + m) where n and m are the lengths of the two arrays

Space Complexity: O(min(n, m)) - the map stores at most min(n, m) unique elements

Time and Space Complexity

Why O(n)? We iterate through each element exactly once. HashMap operations (put, get, containsKey) are O(1) on average.

Why O(k) or O(1) space? For hash maps, we store at most k unique elements. For fixed-size arrays, space is constant regardless of input size.