Frequency Counting with HashMaps

Welcome back! In our last session, we mastered the sliding window technique for efficiently solving problems on contiguous subarrays. We ended with a preview of how other data structures can enhance this pattern. Today, we'll dive deep into that idea by tackling another essential interview pattern you've prioritized: solving frequency-counting problems using a HashMap.

This lesson is all about a simple but powerful idea: how many times does each unique item appear in a collection? You'll learn why HashMap is the perfect tool for this task in Java, how to implement the counting logic efficiently, and how this pattern serves as a building block for more complex interview challenges.

1. What is Frequency Counting?

At its core, frequency counting is the process of counting the occurrences of each element in a dataset. Imagine you have an array of numbers, a list of user actions, or a block of text. A frequency-counting algorithm would tell you exactly how many times each number, action, or word appears.

This is a fundamental task in data processing and a very common pattern in coding interviews. The goal is to transform a collection of items into a summary of their frequencies.

This diagram illustrates the goal of frequency counting: taking an input list like `[1, 2, 3, 2, 4, 1]` and producing a count for each unique element.

While you could use nested loops to achieve this (for each element, loop through the entire array again to count its occurrences), this approach has a time complexity of $O (n^{2})$ and is highly inefficient for large datasets. This is where HashMap comes in.

2. Why `HashMap` is the Ideal Tool

From our earlier lesson on Java Collections, you'll recall that a HashMap stores data in key-value pairs. This structure is perfectly suited for frequency counting:

The Key: The element from the array (e.g., the number 10).
The Value: The frequency of that element (e.g., the integer 3).

The power of HashMap lies in its performance. On average, adding a key-value pair (put), retrieving a value by its key (get), and checking if a key exists (containsKey) are all constant-time operations, or $O (1)$ . This allows us to process an entire array in a single pass, leading to a highly efficient linear time complexity of $O (n)$ . Since you have experience with Python, this is directly analogous to using a dictionary (dict) to count frequencies, where items are keys and their counts are values.

Let's watch a short video from the Coding with John channel to quickly refresh our memory on the essential HashMap methods.

Map and HashMap in Java - Full Tutorial

This video provides a great refresher on the core concepts of HashMap.

Focus on these key segments: Declaring and initializing a HashMap, including specifying the generic types for keys and values. Adding key-value pairs using the .put() method. Retrieving a value for a given key using the .get() method. Checking for a key's existence with .containsKey(). An important note on using wrapper classes (like Integer) instead of primitive types (int).

3. Implementing the Frequency Count Algorithm

Now that we've reviewed the tool, let's outline the algorithm. The logic is straightforward:

Create an empty HashMap that will map elements to their integer counts (e.g., HashMap<Integer, Integer>).
Iterate through each element in the input array.
For each element, check if it already exists as a key in our HashMap.
- If it exists: Get its current count, add 1, and update the map with the new count.
- If it doesn't exist: Add the element to the map as a new key with a count of 1.
After the loop finishes, the HashMap will contain a complete frequency count of all elements.

Let's see this coded live. The following video from CloudTech walks through this exact logic using an if-else block, which is a perfectly valid way to implement it.

Find Count Of Each Element from Array | Java Interview Questions and Answers

This video provides a clear, step-by-step implementation of the frequency counting algorithm in Java.

Watch how the presenter translates the logic into code: Setup: A method is created and a HashMap<Integer, Integer> is initialized. Core Logic: The code iterates through the array, using containsKey() to check for the element and then an if-else block to either update the existing count or put a new entry with a count of 1. Result: The presenter iterates through the final map to print the results and verifies the output.

4. A More Concise Approach: `getOrDefault()`

The if-else logic you just saw works perfectly, but modern Java offers a more elegant and concise method: getOrDefault(key, defaultValue).

This method attempts to get the value for a given key. If the key exists, it returns the corresponding value. If the key does not exist, it returns the defaultValue you provide. This allows us to combine the check, get, and default initialization into a single line.

Here's how our logic changes:

Create an empty HashMap.
Iterate through the array.
For each element e, execute this line:
map.put(e, map.getOrDefault(e, 0) + 1);

Let's break that down:

map.getOrDefault(e, 0) will fetch the current count of element e. If e isn't in the map yet, it will return the default value 0.
We then add 1 to this result.
map.put(...) then sets the new count for element e, whether it was a new or existing entry.

The following resources from takeuforward and CodeSignal explain this optimal approach very well.

Introduction to HashMaps in Java for Counting Occurrences

This article from CodeSignal provides an excellent explanation of using getOrDefault.

Focus on the sections explaining the core logic. First, review the general approach where they describe incrementing the value for an existing element or adding a new one. Then, carefully read the part that introduces the cleaner solution using the getOrDefault method. Notice how it removes the need for an if-else block.

Now, let's look at a complete code example and complexity analysis from takeuforward.

Count frequency of each element in the array - Tutorial - takeuforward

This article provides a full, optimal solution with complexity analysis.

First, review the Algorithm section for a high-level overview. Then, examine the Java code block closely. You'll see the getOrDefault method in action inside the loop. Finally, read the Complexity Analysis section, which confirms the Time Complexity is O(N) and Space Complexity is O(N) in the worst case (where all elements are unique).

5. A Quick Reference

HashMap is versatile. The image below from Java Concept Of The Day provides a handy "cheat sheet" of common HashMap operations, including frequency counting, which you can use as a quick reference.

A summary of common coding patterns using Java's `HashMap`. Note the two boxes for "Frequency of each element..." which implement the pattern we just learned.

Conclusion

You've now added another fundamental pattern to your interview preparation arsenal. Frequency counting is a problem that appears frequently, both on its own and as a component of more complex algorithms.

Here are the key takeaways from today's lesson:

Frequency Counting: The task of determining the number of occurrences of each unique element in a collection.
HashMap is Optimal: It provides an efficient solution with $O (n)$ time complexity, far superior to $O (n^{2})$ brute-force approaches.
The Core Logic: Map elements to their counts. The element is the key, and its frequency is the value.
getOrDefault for Elegance: Use the map.getOrDefault(key, 0) + 1 pattern for clean, concise, and efficient implementation.

In our next lesson, we will tackle one of the most classic interview questions of all time: the "Two Sum" problem. You'll see that the optimal solution to this problem also relies on the clever use of a HashMap, reinforcing just how vital this data structure is for a software engineer's toolkit.

Recommended resources