Frequency Counting
Frequency counting replaces repeated searches with occurrence totals, forming the backbone of anagrams, duplicates, and top-K problems.
Count What Matters
A frequency count records how many times each value appears. Instead of asking whether a value has appeared by scanning the array again, you update a counter during one pass. The stored count becomes the evidence for duplicates, matches, missing values, or majority behavior.
This is one of the most common upgrades from brute force. If the naive solution compares every item to every other item, ask whether counts would let you answer the same question in one or two passes.
Array Counter or HashMap
Use an array counter when the key range is small and known. Lowercase English letters fit in int[26]. ASCII characters fit in int[128]. Small bounded integers can often be shifted into a zero-based index.
Use a HashMap when keys are large, sparse, negative, strings, or otherwise not easy to map into a compact array. The big-O is still usually O(n) expected time, but the constants and memory overhead are higher than a primitive array counter.
Canonical Interview Uses
Anagrams compare character counts. Duplicates check whether a count becomes greater than one. Top-K frequent elements counts values first, then extracts the largest counts with a heap, bucket array, or quickselect-style approach. Sliding-window frequency problems maintain counts as characters enter and leave the window.
The pattern is not limited to equality. Counts can represent inventory, deficits, balances, or how many active intervals share a label. The key is choosing exactly what identity should be counted.
Common Mistakes
The first mistake is using a fixed array counter when the input range is not actually bounded. The second is forgetting to decrement counts when a sliding window shrinks. The third is comparing maps too often instead of tracking how many keys currently match.
For character problems, be explicit about the alphabet. Lowercase-only, case-sensitive, Unicode, and ASCII constraints lead to different counter choices. Do not assume int[26] unless the problem guarantees lowercase English letters.
Count letters with an array and values with a HashMap
Use a primitive counter for a tiny alphabet and a HashMap when values are not compact enough for direct indexing.
Key Takeaways
- Frequency counting stores occurrence totals so later checks do not rescan the input.
- Use **int[26]** or **int[128]** when the alphabet is fixed and small.
- Use a HashMap for sparse, large, negative, or non-integer keys.
- Anagrams, duplicates, sliding-window counts, and top-K frequency all build on this pattern.