menu_bookGyanByte
Lesson 063 min read

Hash Maps & Frequency Counting

November 05, 2026

// TL;DR

A hash map (dict) answers 'have I seen X?' or 'how many times?' in O(1), which turns many O(n²) brute forces into O(n). The Two-Sum insight: walk once, and for each element ask the map 'have I seen the complement (target − current)?' — if yes, done. Hash maps also power FREQUENCY counting (Counter), GROUPING (anagrams keyed by sorted letters), de-duplication, and combine with PREFIX SUMS to count subarrays with a target sum in O(n). Signal: you catch yourself scanning the array again for each element ('for each x, is there a y such that…'). The trade is O(n) extra space for O(n) time. Worked: two-sum, group anagrams, subarray-sum-equals-k.

The hash map is the most useful data structure in interviews. The core move is always the same: remember what you’ve seen so you can look it up in O(1) — turning quadratic searches into linear ones.

The idea

Hash maps, trade memory for O(1) lookups. On an array 2, 7, 11, 15 with target 9, while looking at 7 we keep a map seen of value to index containing 2 at index 0; we need 9 minus 7 equals 2, is 2 in the map? Yes, so the answer is indices 0 and 1. The idea: brute force checks every pair in O(n squared), but instead walk once and keep a hash map of what you've already seen; for each element ask the map in O(1) 'have I seen the complement, target minus current?', turning an O(n squared) search into O(n) time for O(n) space. Hash maps also power frequency counting, grouping like anagrams, and de-duplication. Use it for two-sum, subarray sum equals k, group anagrams, first unique char, contains duplicate, LRU cache.

The classic Two Sum problem: find two numbers that add to a target. The brute force checks every pair — O(n²). The hash-map solution walks the array once, and for each element asks the map a single O(1) question: “have I already seen the complement target − current?” If yes, we have our pair. We store each number as we go.

The template: Two Sum

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:      # O(1): have I seen the complement?
            return [seen[target - n], i]
        seen[n] = i
    return []
# two_sum([2,7,11,15], 9) -> [0, 1]

O(n) time, O(n) space. This single idea — store seen values, look up the complement — solves a large family of “find two things that relate” problems.

Frequency counting and grouping

Hash maps are also how you count and group. Python’s Counter is a hash map specialised for counting:

from collections import Counter, defaultdict

# group anagrams: words that share the same sorted letters
def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))        # anagrams → same key
        groups[key].append(w)
    return list(groups.values())
# group_anagrams(["eat","tea","tan","ate","nat","bat"])
#   -> [["eat","tea","ate"], ["tan","nat"], ["bat"]]

The pattern: choose a key that collapses “equivalent” items together (sorted letters for anagrams, a canonical form for duplicates), and bucket by it.

Worked example: subarray sum equals K (map + prefix sum)

Hash maps combine beautifully with prefix sums (Lesson 7) to count subarrays with a target sum in O(n). Keep a running sum and a map of how many times each running-sum value has occurred; a subarray sums to k whenever running − k has been seen:

def subarray_sum(nums, k):
    count = 0; running = 0
    seen = {0: 1}                       # a prefix sum of 0 seen once (empty prefix)
    for n in nums:
        running += n
        count += seen.get(running - k, 0)   # how many earlier prefixes make a k-sum?
        seen[running] = seen.get(running, 0) + 1
    return count
# subarray_sum([1,1,1], 2) -> 2

Step-by-step walkthrough

Trace Two Sum on nums = [3, 2, 4, 7], target = 6. For each number we ask the map one question — have I already seen the complement? — then remember the current number.

i nums[i] need = target − x need in map? map {value: index} so far
0 3 3 no {}
1 2 4 no {3:0}
2 4 2 yes → answer {3:0, 2:1}

At i = 2 the complement 2 is already in the map at index 1, so the answer is [1, 2] — one pass, O(n), instead of checking every pair.

When to reach for it

Signals: you need to ask “have I seen …?” or “how many times …?” quickly; you catch yourself writing a nested loop that re-scans the array for each element; you need to group or de-duplicate; or you need O(1) lookups by key. Hash maps also underpin more complex structures — an LRU cache is a hash map plus a doubly-linked list.

Pitfalls

  • Storing before checking (or vice-versa). In Two Sum, check the complement before inserting the current element, or you may match an element with itself.
  • Unhashable keys. Lists/dicts can’t be dict keys; convert to a tuple or string (e.g. tuple(sorted(...))).
  • Memory. The map is O(n) space. If the interviewer wants O(1) space and the array is sorted, use two pointers (Lesson 3) instead.

Recap

A hash map answers “seen it?” and “how many?” in O(1), turning O(n²) searches into O(n) at the cost of O(n) space. The Two-Sum insight (look up the complement), frequency counting (Counter), grouping (bucket by a canonical key), and map + prefix sum (count subarrays) cover a huge range of questions. Signal: re-scanning the array for each element, or count/group/seen.

Practice: 13 solved problems on hash maps → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 7 — Prefix Sums, for O(1) range queries.

exercisePractice this patternHash Maps & Frequency — Practice Problemsarrow_forward
coding-interviewhash-mapfrequencypython
arrow_back PreviousFast & Slow PointersNext arrow_forwardPrefix Sums