Module 5.2 ⏱ 40 min read ⚡ Hash Maps & Frequency Tracking

Frequency Maps & Custom Objects

Master state tracking using hash sets and maps, and learn how to design hash keys for complex structures and custom objects.

1. State Tracking with Hash Sets and Maps

Hash maps and sets excel at maintaining running frequencies, detecting duplicates, and storing historical states for fast $O(1)$ lookups. By transforming complex sequential conditions into dictionary counts or lookup checks, algorithms can bypass nested loops and drop from $O(n^2)$ down to $O(n)$ time complexity.

Frequency Counting: Using hash tables to tally element occurrences allows for efficient subset matching, anagram grouping, and window tracking.

2. Hashing Complex Structures & Custom Objects

Standard hash tables natively support primitive data types like integers, floats, and strings. However, when working with composite keys—such as pairs, vectors, tuples, or custom class instances—languages require specialized hash functions and equality operators. In C++, this involves custom `std::hash` specializations, while Python uses tuple packing and immutable type constraints.

// C++ Solution: Group Anagrams (Frequency Map / Sorted Key Mapping)
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {
        std::unordered_map<std::string, std::vector<std::string>> map;
        for (std::string s : strs) {
            std::string key = s;
            std::sort(key.begin(), key.end());
            map[key].push_back(s);
        }
        std::vector<std::vector<std::string>> result;
        for (auto& pair : map) {
            result.push_back(pair.second);
        }
        return result;
    }
};
            

# Python Solution: Group Anagrams (Frequency Map / Sorted Key Mapping)
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        mapping = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            mapping[key].append(s)
        return list(mapping.values())
            

// Java Solution: Group Anagrams (Frequency Map / Sorted Key Mapping)
import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for Two-Sum variations and Group Anagrams.

Quick Check: Test Your Intuition

What is the overall time complexity of grouping anagrams for $n$ strings, where each string has a maximum length of $k$, using sorted character strings as hash keys?