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.

Frequency counting reduces 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.

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

Anagram Detection: Instead of sorting both strings to compare in O(n log n), we count characters in each string and compare the counts in O(n). For very small alphabets (e.g., 26 lowercase letters), sorting is also O(n) on small inputs and can be faster in practice due to cache locality; the HashMap form generalizes to large alphabets.

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.

Many problems do not depend on order. When order is irrelevant, frequency counting captures all the information we need.

Reach for frequency counting when a problem shows one of these signals:

1. Mentions of "anagram" or "permutation"

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

2. Questions about "duplicates" or "unique elements"

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

3. Comparing composition rather than order

If you need to check whether two collections have the same elements regardless of order, frequency counting fits well.

4. Anything asking about "occurrence count" or "frequency"

A problem that explicitly asks how many times something appears is a direct frequency counting problem.

5. Matching or grouping by content

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

Common problem types where frequency counting applies:

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.

Good fit for: 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.

Reach for this when comparing the composition of two collections, or checking whether they are anagrams or permutations.

Variant 3: Increment/Decrement Pattern

Use a single map with increment for one collection and decrement for another. First check that both strings have the same length. Then iterate: increment counts from string A, decrement from string B. If any count goes negative, return false immediately (B has a character A does not have enough of). At the end, all counts will be zero.

Prefer this approach when memory matters, or when one of the inputs arrives as a stream.

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.

Works well for lowercase letters (26 slots), uppercase letters (26 slots), ASCII characters (128 slots), or digits (10 slots).

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:

The right counter depends on the input alphabet and the operations needed. Picking wrong wastes memory, slows the code, or silently produces wrong answers on non-ASCII input.

A few caveats worth knowing before you reach for c - 'a' indexing on every problem:

When in doubt, start with a HashMap. Switch to an array only when the alphabet is small, fixed, and the workload is hot enough that the constant-factor speedup matters.

Modern languages provide built-in counter idioms that are shorter and clearer than rolling your own increment-or-insert logic. Knowing the native form for your language avoids three-line ceremony for what should be one line.

For the most-common-element operation, Python's Counter.most_common(k) is the simplest cross-language reference. Every other language requires either an explicit sort by value or a heap of size k. Java's merge form is the cleanest non-Python option because it folds the read, default, and write into a single atomic step. C# 8 onward has GetValueOrDefault, which removes the TryGetValue ceremony seen in older code.

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

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

A HashSet works here because we only care whether the count is greater than zero, not the exact count.

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

The O(n) time comes from iterating through each element exactly once. HashMap operations (put, get, containsKey) are O(1) on average.

The space cost depends on the structure. Hash maps store at most k unique elements, giving O(k). Fixed-size arrays use constant space regardless of input size.

Group Anagrams (LeetCode 49) asks: given a list of strings, group strings that are anagrams of each other. The naive approach compares every pair with frequency counts, costing O(n^2 * k) where n is the number of strings and k is the average string length.

The fingerprint trick collapses this to O(n k log k) or O(n k). For each string, compute a canonical key that all its anagrams share, then group strings by key in a HashMap. Two strings end up in the same bucket if and only if they are anagrams.

Two common keys work for this:

The sorted-string approach is shorter and easier to read, so it is the standard interview answer. The count-tuple variant is the right choice when strings are long enough that the log k factor starts to hurt.

For very long strings, build a 26-tuple frequency array as the key, O(k) instead of O(k log k). For Unicode input, switch to a HashMap-based count tuple or stick with sorted code points.

The single most important interview application of frequency counting is inside a sliding window. The pattern looks the same across most problems:

Canonical problems that follow this pattern:

A general template in Java:

Removing zero-count keys keeps windowCount.size() equal to the number of distinct characters in the current window, which several problems (LC 3, LC 340) depend on directly. For the broader pattern mechanics, see the sliding window introduction chapter.

Top K Frequent Elements (LeetCode 347) asks for the k most frequent values in an array. The standard approach combines a HashMap with a min-heap of size k.

The flow is:

Total cost: O(n) for the map and O(m log k) for the heap, where m is the number of unique values. Space is O(m + k).

A follow-up worth knowing: bucket sort by frequency runs in O(n). Create n + 1 buckets indexed by frequency, place each unique value in its frequency bucket, then read buckets from the highest index down until k values are collected. The heap version remains the interview-standard answer because it generalizes cleanly to streaming top-k.

Frequency counting combines with prefix sums for problems where the question is "how many subarrays satisfy some condition on their sum." Subarray Sum Equals K (LeetCode 560) is the canonical example.

Define prefixSum[i] as the sum of nums[0..i]. A subarray ending at index i with sum k corresponds to some earlier index j where prefixSum[j] = prefixSum[i] - k. So the question becomes: at each i, how many earlier prefix sums equal prefixSum[i] - k?

Use a HashMap from prefix sums to their counts, initialized with {0: 1} for the empty-prefix base case. At each position, increment the answer by the count of prefixSum - k already in the map, then increment the count for the current prefixSum. The whole algorithm is O(n) time and O(n) space.

The same pattern unlocks several other problems:

For the broader prefix-sum mechanics (sliding running totals, mod arithmetic, edge cases at index 0), see the prefix sum chapter.

A small but useful extension: for problems like Least Number of Unique Integers after K Removals (LC 1481) or Sort Characters By Frequency (LC 451), the first step is a normal frequency map, and the second step is a count of how many values share each frequency.

Build the frequency map first, then either sort the counts or build a second map from frequency to a list of values. For LC 1481, sorting frequencies ascending and removing the smallest ones first minimizes how many unique values get fully erased. For LC 451, grouping characters by frequency lets you emit the most common ones first.

This count-of-counts step is a one-line extension that often unlocks the next layer of analysis on top of a basic frequency count.