Pattern 6 of 27
Hashing and Frequency Maps
Trade memory for speed by storing what you have already seen in a hash map or set, turning repeated searches into constant-time lookups.
- Cost
- O(n) average time, O(n) space
- Problems
- 6
When to reach for it
- A brute force would search the rest of the array for every element.
- The prompt is about duplicates, counts, anagrams, or complements.
- Only membership or frequency matters, not order.
How it works
Most O(n²) array questions hide a lookup: for this element, does its partner exist somewhere? A hash map answers that in O(1) on average, so one pass that checks for the complement before storing the current element replaces the nested loop. Frequency maps extend the idea from presence to counts, and a canonical key, such as a word's sorted letters, groups together things that should be treated as equal.
The template
Written for Two Sum (write-up)
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
return []Six problems, in learning order
- 1.Two SumLeetCode 1Check for target minus x before storing x.Easy
- 2.Group AnagramsLeetCode 49Key each word by its sorted letters, or by a tuple of 26 letter counts.Medium
- 3.Longest Consecutive SequenceLeetCode 128Only start counting from numbers whose predecessor is missing from the set.Medium
- 4.Contains DuplicateLeetCode 217A set that already holds the element answers the question.Easy
- 5.Valid AnagramLeetCode 242Two equal frequency maps, or one map counted up for s and down for t.Easy
- 6.Top K Frequent ElementsLeetCode 347Count, then bucket values by frequency to avoid a full sort.Medium
What usually goes wrong
- Storing the current element before checking for its complement, which pairs an element with itself.
- Using a mutable list as a dictionary key in Python.
- Treating O(1) as guaranteed; crafted inputs can degrade some hash tables.
Hashing and Frequency Maps, answered
When should I use the hashing and frequency maps pattern?
A brute force would search the rest of the array for every element. The prompt is about duplicates, counts, anagrams, or complements. Only membership or frequency matters, not order.
What is the time complexity of hashing and frequency maps?
O(n) average time, O(n) space. Frequency maps extend the idea from presence to counts, and a canonical key, such as a word's sorted letters, groups together things that should be treated as equal.
Which problem should I start with for hashing and frequency maps?
Start with Two Sum (LeetCode 1, Easy). Check for target minus x before storing x. The six problems on this page are in learning order.