Counting & Frequency
Frequency maps solve a startling range of problems - first unique, majority element, top-k - in a single pass.
On this page
A surprising number of interview problems reduce to one move: count how many times each thing appears, then read answers off the counts. A frequency map (or a frequency array) does this in a single O(n) pass, and recognizing when a problem is secretly a counting problem is a fast path to the solution.
The frequency map
Build a Map<K, Integer> of counts in one pass. Java's merge and getOrDefault make it clean:
// count occurrences of each element — O(n)
Map<Integer, Integer> count = new HashMap<>();
for (int x : a)
count.merge(x, 1, Integer::sum); // count[x] = count.getOrDefault(x, 0) + 1For a small, known domain (lowercase letters, digits, bytes), a plain int[] is faster and uses
less memory than a map - count[c - 'a']++ for letters. Reach for a map only when the key space is
large or unknown.
What counting unlocks
Once you have the counts, many questions are a second, simple pass:
- First unique element - scan the original order, return the first with count 1.
- Majority element - the one with count > n/2.
- Anagrams - two strings are anagrams iff their counts match.
- Top-k frequent - the k keys with the highest counts (a heap or bucket sort over the counts).
// first non-repeating character — O(n): count, then scan in order
int firstUniqChar(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
for (int i = 0; i < s.length(); i++)
if (count[s.charAt(i) - 'a'] == 1) return i;
return -1;
}Two passes, both O(n): one to count, one to find the answer. The counting map turned an O(n²) "for each character, scan the rest" into O(n).
merge, getOrDefault, computeIfAbsent
Learn these three Map methods - they make counting and grouping terse and readable.
count.merge(k, 1, Integer::sum) increments a counter; map.getOrDefault(k, 0) reads with a default;
map.computeIfAbsent(k, x -> new ArrayList<>()).add(v) appends to a list-valued map without a null
check. Fluency here makes your interview code noticeably cleaner.
To find the most common answer at an event, you don't compare every attendee to every other (O(n²)). You keep a tally sheet and add a mark next to each answer as people arrive - one pass. At the end, the tallest column is your answer at a glance. A frequency map is that tally sheet: one walk past the data marking counts, then read the results straight off the totals.
Given an array, return the k most frequent elements. Describe the two phases of the solution and give an approach that avoids fully sorting all the counts.
A problem asks for the 'first non-repeating character.' What's the efficient approach?
Key takeaways
- Many problems reduce to counting occurrences, then reading answers off the counts.
- Build a frequency map in one O(n) pass with merge/getOrDefault; use an int[] for small fixed domains like letters.
- Counting unlocks first-unique, majority element, anagram checks, and top-k frequent.
- Learn Map.merge, getOrDefault, and computeIfAbsent for clean counting and grouping code.
- Frequencies are bounded by n, so bucket sort can select top-k in O(n) without fully sorting.