Common Hashing Patterns
Common hashing patterns in coding interviews primarily include frequency counting and prefix sum with hashing. Frequency counting utilizes a hash table to efficiently count occurrences of elements in a single pass, allowing O(1) access for frequency queries. This pattern is ideal for problems involving counts or comparisons of collections. Conversely, prefix sum with hashing tracks running sums to identify subarrays with a specific sum, reducing the complexity from O(n²) to O(n). Recognizing the problem type is crucial: use frequency counting for counts and compositions, and prefix sums for subarray sum conditions.
Recognizing a hash table as the right data structure is only the first step. The next is knowing which pattern to apply. This lesson covers the two most important hashing patterns in coding interviews: frequency counting and prefix sum with hashing. Together, they cover the majority of hash table-based interview problems.
Interview lens: Both patterns share a common signal: repeated lookup or counting over a sequence. Any problem that requires us to know how many times something appeared, or whether a subarray with a given sum exists, is almost certainly one of these two patterns. Spotting that signal early and reaching for a hash table is the reflex this lesson builds.
Frequency counting
The frequency counting pattern uses a hash table to count how many times each element appears in a collection during a single pass. We map each unique element to its count, incrementing the count each time we encounter the element. Once the pass is complete, the hash table gives us
This pattern eliminates the need for nested loops. Without a hash table, counting occurrences of every element requires an