Hash Maps for O(1) Frequency Counting

1. The Frequency Counting Pattern

At its core, frequency counting is exactly what it sounds like: counting the occurrences of elements in a collection. This simple idea is incredibly powerful. Many complex-sounding problems, which might naively suggest an $O(n^2)$ solution (like comparing every element to every other element), can be simplified to a linear $O(n)$ solution by first counting frequencies.

The key insight is that for problems where the order of elements doesn't matter, their frequency distribution is often all the information you need.

The data structure that enables this efficiency is, of course, the hash map. By using a hash map, we can iterate through a collection of $n$ items and build a complete frequency count in $O(n)$ time, because each of the $n$ updates to the map is an $O(1)$ average time operation. This is a classic example of a time-space tradeoff: we use extra space (the hash map) to achieve a much faster runtime.

2. The Core Implementation: Building a Frequency Map

The fundamental pattern for building a frequency map (or "frequency counter") is a loop and a hash map. Let's see how this looks in practice.

Given your proficiency in Python, you have several ways to implement this, each with its own level of elegance. Let's consider an example: counting character frequencies in the string "hello world".

Method 1: The Basic if/else
This is the most explicit implementation, mirroring the logic from the video.

s = "hello world"
freq_map = {}
for char in s:
    if char in freq_map:
        freq_map[char] += 1
    else:
        freq_map[char] = 1
# Result: {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Method 2: Using dict.get()
A slightly more concise way is to use the get() method with a default value. freq_map.get(char, 0) will return the current count of char if it exists, or 0 if it doesn't.

s = "hello world"
freq_map = {}
for char in s:
    freq_map[char] = freq_map.get(char, 0) + 1

Method 3: Using collections.defaultdict
This is the most idiomatic and efficient Python approach for this pattern. You initialize a defaultdict with a factory function (like int, which defaults to 0). When you try to access a key that doesn't exist, it's automatically created with the default value, eliminating the need for checks.

from collections import defaultdict

s = "hello world"
freq_map = defaultdict(int)
for char in s:
    freq_map[char] += 1

Using defaultdict makes your code cleaner and avoids the common KeyError.

3. Application: Solving "Valid Anagram"

Now let's apply this pattern to solve a classic interview problem: Valid Anagram.

Problem Statement: Given two strings, s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

• Input: s = "anagram", t = "nagaram"

• Output: true

• Input: s = "rat", t = "car"

• Output: false

How can we solve this using frequency counting? The definition of an anagram gives us the answer: two strings are anagrams if and only if they have identical character frequencies.

So, the algorithm is:

1. Check if the strings have different lengths. If so, they can't be anagrams.
2. Create a frequency map for the first string, s.
3. Iterate through the second string, t, and decrement the count for each character in the map.
4. If at any point a character from t is not in the map, or its count is already zero, they are not anagrams.
5. After iterating through t, if all counts in the map are zero, they are anagrams.

A more direct comparison is even simpler: build a frequency map for s and another for t, and then simply check if the two maps are equal.

Here's how you might implement the two-map comparison in Python, using defaultdict for clean code:

from collections import defaultdict

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    s_counts = defaultdict(int)
    for char in s:
        s_counts[char] += 1

    t_counts = defaultdict(int)
    for char in t:
        t_counts[char] += 1
    
    return s_counts == t_counts

# --- Analysis ---
# Time Complexity: O(n), where n is the length of the strings. 
# We iterate through each string once to build the maps (O(n) + O(n)). 
# Comparing the maps also takes O(k) time, where k is the number of unique characters (at most 26 for lowercase English, so effectively O(1)).
#
# Space Complexity: O(k), where k is the number of unique characters.
# We store at most k unique characters in our hash maps. For a fixed alphabet (like ASCII or lowercase English), this can be considered O(1) space.

Another common and clever implementation in Python uses collections.Counter, which is a specialized dictionary subclass for counting hashable objects.

from collections import Counter

def is_anagram_counter(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

This single line does exactly what our manual defaultdict implementation did. Knowing about Counter is a great sign of Python fluency in an interview.

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    anagram_groups = defaultdict(list)
    
    for s in strs:
        # The sorted tuple of characters serves as a hashable key
        key = tuple(sorted(s))
        anagram_groups[key].append(s)
        
    return list(anagram_groups.values())

# Example Walkthrough:
# 1. s = "eat" -> key = ('a', 'e', 't') -> anagram_groups[('a', 'e', 't')] = ["eat"]
# 2. s = "tea" -> key = ('a', 'e', 't') -> anagram_groups[('a', 'e', 't')] = ["eat", "tea"]
# 3. s = "tan" -> key = ('a', 'n', 't') -> anagram_groups[('a', 'n', 't')] = ["tan"]
# 4. s = "ate" -> key = ('a', 'e', 't') -> anagram_groups[('a', 'e', 't')] = ["eat", "tea", "ate"]
# ... and so on.

Conclusion

You've now learned one of the most fundamental and frequently applied patterns in coding interviews. By leveraging the $O(1)$ average lookup time of hash maps, you can solve a wide range of problems in linear time that would otherwise be much slower.

Key Takeaways:

• Frequency Counting Pattern: A technique to solve problems by counting element occurrences, especially useful when element order is irrelevant.
• The Right Tool: Hash maps (or Python's dict, defaultdict, Counter) are the ideal data structure for this pattern, enabling you to build a frequency map in $O(n)$ time.
• Problem Recognition: Look for keywords like "anagram," "duplicate," "unique," or problems comparing the composition of two collections. This is your cue to consider frequency counting.
• Complexity: The pattern typically results in an $O(n)$ time complexity and $O(k)$ space complexity, where $n$ is the number of elements and $k$ is the number of unique elements.

In our next lesson, we will continue exploring the power of hash maps by tackling another iconic interview problem: Two Sum. You'll see how a similar "have I seen this before?" logic can be used to find pairs of elements that satisfy a certain condition.