Zählen & Häufigkeit
Häufigkeitskarten lösen erstaunlich viele Probleme - erstes eindeutiges Element, Mehrheitselement, Top-k - in einem einzigen Durchlauf.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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.