One of the most powerful uses of a Hash Map is to count the frequency of elements. Whether you are finding the most popular product, detecting anagrams, or analyzing DNA sequences, this pattern is your best friend.
The Core Idea
Iterate through your data and build a map where:
Key: The element (character, number, string).
Value: The count (frequency).
The Grocery Store Analogy
Think of a frequency map like taking inventory at a grocery store. You walk down the aisle with a clipboard. For every apple you see, you don't write down "apple, apple, apple". Instead, you find the "Apple" row on your clipboard and add a tally mark. The Key is the item (Apple), and the Value is the tally count. This turns a linear scan of O(N) items into an O(1) lookup map.
Java
Go
```java
Map<String, Integer> counts = new HashMap<>();
for (String item : items) {
counts.put(item, counts.getOrDefault(item, 0) + 1);
}
```
```go
counts := make(map[string]int)
for _, item := range items {
counts[item]++
}
```
Interactive Anagram Checker
An Anagram is a word formed by rearranging the letters of another (e.g., “listen” and “silent”).
How do we check if two strings are anagrams? By comparing their character frequency maps!
Anagram Visualizer
Map 1
Map 2
Problem 1: Group Anagrams (LeetCode 49)
Given an array of strings, group the anagrams together.
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
The Strategy
We need a Key that represents the anagram group. All anagrams must map to this same key.
Approach 1: Sorted String Key
Sort "eat" → "aet". Sort "tea" → "aet". The sorted string becomes the Hash Map key.
Approach 2: Character Count Key
Count character occurrences to form a string like "1#0#0#...#1" representing 'a' to 'z'.
Step-by-Step Example (Sorted String)
Input: ["eat", "tea", "bat"]
Read "eat". Sorted: "aet". Add to map: {"aet": ["eat"]}
| Approach | Time Complexity | Space Complexity | Notes |
| :— | :— | :— | :— |
| Sorted String Key | O(N * K log K) | O(N * K) | Where N is the number of strings, and K is the maximum length of a string. |
| Character Count Key | O(N * K) | O(N * K) | More efficient for very long strings. |
Java
Go
```java
public List<List> groupAnagrams(String[] strs) {
Map<String, List> groups = new HashMap<>();
for (String s : strs) {
// Sort the string to form the key
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.putIfAbsent(key, new ArrayList<>());
groups.get(key).add(s);
}
return new ArrayList<>(groups.values());
}
```
</div>
```go
func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, s := range strs {
// Sort the string to form the key
chars := []rune(s)
sort.Slice(chars, func(i, j int) bool {
return chars[i] < chars[j]
})
key := string(chars)
groups[key] = append(groups[key], s)
}
res := make([][]string, 0, len(groups))
for _, v := range groups {
res = append(res, v)
}
return res
}
```
</div>
## Problem 2: Top K Frequent Elements (LeetCode 347)
Given an integer array `nums` and an integer `k`, return the `k` most frequent elements.
### The Strategy
1. **Count Frequencies**: Use a Hash Map to count occurrences of each number.
2. **Sort by Frequency**: Use a Max Heap (O(N log K)) or Bucket Sort (O(N)).
**Bucket Sort Approach (O(N)):**
Since the frequency of an element cannot exceed the total number of elements `N`, we can create an array of lists (buckets) where the index `i` stores a list of numbers that appear exactly `i` times.
#### Step-by-Step Example (Bucket Sort)
Input: `nums = [1, 1, 1, 2, 2, 3], k = 2`
1. **Count Frequencies**: Map becomes `{1: 3, 2: 2, 3: 1}`.
2. **Fill Buckets**: Create array of length `N + 1` (length 7).
- Index 1: `[3]` (appears 1 time)
- Index 2: `[2]` (appears 2 times)
- Index 3: `[1]` (appears 3 times)
3. **Gather Top K**: Iterate buckets backwards from length 6 down to 0. We find `1` at index 3, and `2` at index 2. Return `[1, 2]`.
#### Complexity Analysis
| Approach | Time Complexity | Space Complexity | Notes |
| :--- | :--- | :--- | :--- |
| **Hash Map + Heap** | O(N log K) | O(N) | Good general approach, robust for unbounded ranges. |
| **Hash Map + Bucket Sort** | O(N) | O(N) | Optimal approach since max frequency is bounded by N. |
Java
Go
```java
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
List[] freq = new List[nums.length + 1];
// 1. Count frequencies
for (int n : nums) {
count.put(n, count.getOrDefault(n, 0) + 1);
}
// 2. Fill buckets
for (int i = 0; i < freq.length; i++) freq[i] = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
freq[entry.getValue()].add(entry.getKey());
}
// 3. Gather top k
int[] res = new int[k];
int idx = 0;
for (int i = freq.length - 1; i > 0; i--) {
for (int n : freq[i]) {
res[idx++] = n;
if (idx == k) return res;
}
}
return res;
}
```
</div>
```go
func topKFrequent(nums []int, k int) []int {
count := make(map[int]int)
freq := make([][]int, len(nums)+1)
// 1. Count frequencies
for _, n := range nums {
count[n]++
}
// 2. Fill buckets
for n, c := range count {
freq[c] = append(freq[c], n)
}
// 3. Gather top k
res := make([]int, 0, k)
for i := len(freq) - 1; i > 0; i-- {
for _, n := range freq[i] {
res = append(res, n)
if len(res) == k {
return res
}
}
}
return res
}
```
</div>
---
Found this lesson helpful?
Mark it as mastered to track your progress through the course.