Hash Set / Map PatternsCounting and deduplication
Two Sum and Group Anagrams — the "trade space for time" pattern.
Used for: Frequency counts, pairing lookups
01Why it exists
Reconciling accounts means asking which two amounts sum to 1000. Enumerating every pair with two nested loops is O(n²), which is ten billion steps for a hundred thousand rows.
Why this fitsAt each row, ask "have I already seen the number I need?" Store what you have seen in a hash table and that question costs O(1), making the whole scan O(n). This is Two Sum, the prototype for every pair-lookup problem.
listen and silent are built from the same letters. Spell checkers, word games and duplicate-document detection all need a fast answer to "same contents, different order".
Why this fitsCount how often each letter appears; if the two count tables match, the words belong together. A hash table makes the counting O(n), and using the sorted string as a key groups every anagram in a single pass.
Hundreds of millions of log lines, and you want the ten most common error messages.
Why this fitsOne O(n) counting pass with a hash table, then take the top k. Frequency counting is the most common use a hash table gets, and pairing it with a heap is the classic Top-K problem.
Reach for it when you see:How many times something appears, whether there are duplicates, finding a partner or a pair, grouping things that belong together, have I seen this before, replacing the inner loop of an O(n²) solution.
02The core idea
A hash table does exactly one thing: O(1) storing and O(1) lookup. Its power comes from one fixed move. A brute-force solution usually has an inner loop that is searching for something; replace that loop with a hash table lookup and O(n²) becomes O(n). You trade O(n) of space for one factor of n.
Almost every problem of this kind is one of four patterns. Pair lookup: at x, ask whether target − x has been seen (Two Sum). Counting: the key is the element and the value is its count (Valid Anagram, Top K Frequent). Grouping: design a key that every member of a group computes to identically (Group Anagrams uses the sorted string). Membership: dump everything into a set up front, and any "is it there" is O(1) afterwards (Longest Consecutive Sequence).
Designing the key is the core skill here. A key has to be hashable — immutable, so a number, a string or a tuple, never a list — and it has to be the same within a group and different between groups. The sorted string, a 26-letter count tuple, a coordinate divided by the cell size, and the value of a prefix sum are all common keys.
03The algorithm
- 1Write the brute-force solution first and find the inner loop that is searching for something. What is it searching for? That is your hash table key.
- 2Decide what the value is: a
setwhen you only need "is it there"; value -> index when you need positions; value -> count when you need frequencies; key -> list when you are grouping. - 3Make a single left-to-right pass: look up first to see whether the table already answers the question, then store the current element. Doing it the other way round lets an element pair with itself.
- 4For grouping problems, design the key first: what operation turns every member of a group into the same value? Make sure that value is an immutable type.
- 5Check the complexity: n iterations, each with an O(1) lookup and store, so O(n) time and O(n) space. If an inner loop is still there, the key is wrong.
04Interactive demo
Two Sum, one pass over the array, step by step: each step first checks whether the partner it needs is in the table, and stores itself when it is not. Note that by the time the answer turns up, the array has been read exactly once.
1def two_sum(nums, target):2 seen = {}3 for i, x in enumerate(nums):4 need = target - x5 if need in seen:6 return [seen[need], i]7 seen[x] = i
05Code
Four snippets for the four patterns. Python's Counter and defaultdict are the standard tools for counting and grouping; C++ uses unordered_map and unordered_set.
from collections import Counter, defaultdict
# Pattern 1: pair lookup. At x, ask "have I already seen the partner I need?"
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i # look up first, store after, or x pairs with itself
# Pattern 2: counting. How many times does a character or a number appear?
def is_anagram(s, t):
return Counter(s) == Counter(t) # a Counter is just dict[element, count]
def top_k_frequent(nums, k):
freq = Counter(nums)
return [x for x, _ in freq.most_common(k)]
# Pattern 3: grouping. Design a key that comes out the same for everything in a group
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
key = "".join(sorted(w)) # "eat", "tea" and "ate" all become "aet"
groups[key].append(w)
return list(groups.values())
# Pattern 4: O(1) membership with a set, turning O(n²) into O(n)
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 not in s: # only count up when x starts a run
length = 1
while x + length in s:
length += 1
best = max(best, length)
return best # each number is visited at most twice -> O(n)06Practice
- LeetCode 1Two Sum (pair lookup)Easy
- LeetCode 242Valid Anagram (counting)Easy
- LeetCode 219Contains Duplicate II (value -> most recent index)Easy
- LeetCode 49Group Anagrams (grouping)Medium
- LeetCode 347Top K Frequent Elements (counting plus buckets or a heap)Medium
- LeetCode 128Longest Consecutive Sequence (membership)Medium