ReviseAlgo Logo

Hash Maps & Sets

Frequency Counting

Master the frequency mapping pattern to track element occurrences, find uniqueness, and solve anagram and grouping problems.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is Frequency Counting?

Frequency Counting is the process of counting how many times each element appears in a collection. By storing elements as keys and their counts as values in a HashMap, we can perform this mapping in linear time.

Why is it Important?

Without a HashMap, counting elements requires nested loops, taking O(N²) time. A frequency map achieves this in O(N) time. It is the building block for resolving anagrams, checking uniqueness, and identifying popular elements.

Where is it Used?

  • Text Editors: Building word counts and autocomplete list registries.
  • Data Streaming Logs: Counting occurrences of incoming page-view event IDs.

    • 2. Mental Model: The Tally Sheet

    Imagine you are counting votes in an election:

  • Instead of sorting the ballots or searching all ballots for each candidate, you write the candidates' names on a whiteboard.
  • As you draw each ballot, you find the candidate's name on the board and add a tally mark (incrementing their count by 1).
  • This is a single-pass process taking time proportional only to the number of ballots.

    • 3. Core Algorithms & Implementations

    Let's look at two standard interview implementations of this pattern.

    1. First Unique Character in a String (LeetCode 387)

    Find the first non-repeating character in a string.
  • First Pass: Build the character frequency map.
  • Second Pass: Traverse the string characters again and check the map for a count of 1.

    • 2. Group Anagrams (LeetCode 49)

    Group strings that are anagrams of each other.
  • For each string, sort its characters to create a unique signature (key).
  • Group strings containing the same signature under the same list value in a HashMap.

    • 4. Visual Trace: Group Anagrams

    Let's group ["eat", "tea", "tan", "ate", "nat"]:

    5. Real-World Applications

  • Histogram Generators: Calculating pixel color distributions in image files.
  • Log Rate-Limiters: Tracking request IPs and rejecting users making more than N requests per minute.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

  • "Write an algorithm to check if two strings are anagrams." -> Build a character frequency array or map, then compare.
  • "Find the top K most frequent elements." -> Build a frequency map, then push entries into a Min-Heap (priority queue) of size K.

    • Common Mistakes

    Warning: 1. Character Array vs. HashMap: For ASCII string character checks, using a full HashMap introduces object wrapping overhead. A simple size-256 integer array (int[] count = new int[256]) is much faster and uses less memory.
    > 2. Duplicate Sorting in Group Anagrams: Sorting long words takes O(L log L) time. If the alphabet is small, you can represent the signature by a character count string (e.g. 2a1b0c...) to achieve linear O(L) key generation.

    7. Summary

  • Complexity: Frequency mapping takes O(N) time and O(N) space.
  • Character Arrays: Use fixed-size primitive arrays for basic character frequencies instead of custom hashmaps.
  • Anagram Signatures: Custom sorted keys group identical character configurations.

    • 8. Quiz

    Question 1: What is the optimal time complexity to check if two strings of length N and M are anagrams? Answer: O(N) if N = M. We count character frequencies of the first string, then subtract counts using the second. If any count goes below zero or lengths differ, they are not anagrams.
    Question 2: Why is a primitive size-26 integer array faster than a HashMap for counting lowercase English letters? Answer: A primitive array has zero lookup overhead, no hashing collisions, no dynamic resizing, and no object wrapping (autoboxing) costs. Lookups are direct memory offsets.
    Question 3: How does the LinkedHashMap in Java help when finding the first unique character? Answer: A LinkedHashMap maintains the insertion order of keys. If we insert characters in order, we can find the first unique key by checking only the keys of the map in order, rather than traversing the entire original string a second time.
    Question 4: True or False: Python's Counter automatically returns 0 for keys that don't exist. Answer: True. collections.Counter behaves like a defaultdict returning 0 for any missing key count queries, preventing KeyError exceptions.
    Question 5: What is the complexity of grouping N words of average length L using sorted-string keys? Answer: O(N × L log L) time, since we sort each of the N words of length L.