readyforhires
Sign up free

Hash Map & Set 101

Fundamental · 4 chapters · 8 min read · Turn slow nested loops into one pass by remembering what you have already seen.

Practise this in the app All guides

What hashing buys you

Constant-time lookup

A hash map stores key-value pairs and finds a key in O(1) time on average. A hash set is the same thing without values: it answers "have I seen this before?" in O(1). In Python these are dict and set, with helpers in collections such as Counter and defaultdict.

The trade is memory for time. A brute-force solution that compares every pair costs O(n²); storing what you have seen in a map usually brings it down to O(n) time with O(n) extra space. In most interviews that trade is exactly what is expected.

Signals in a problem statement

What can be a key

Keys must be hashable: numbers, strings, tuples of hashable things, and frozenset. Lists and dicts cannot be keys. When you need a list as a key, convert it to a tuple; for example, a 26-length tuple of letter counts is a perfect key for grouping anagrams.

The mental model

Walk the input once. At each step, ask: "What do I need to know about the elements before this one?" Store exactly that in the map, keyed by whatever you will look it up with later.

Core patterns with templates

1. Seen-before lookup (complement)

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

Insert after checking so an element is never paired with itself.

2. Frequency counting

from collections import Counter

def can_construct(note, magazine):
    have = Counter(magazine)
    for ch in note:
        if have[ch] == 0:
            return False
        have[ch] -= 1
    return True

3. Group by canonical key

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

For lowercase words, a tuple of 26 counts avoids the sort and makes each key O(length).

4. Last index within a window

def nearby_duplicate(nums, k):
    last = {}
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

5. Start only at the beginning of a run

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best

Each number is visited by the inner loop at most once, so the total is O(n). Example: [100, 4, 200, 1, 3, 2] starts runs only at 1, 100 and 200, giving 4.

6. Bijection with two maps

For isomorphic strings, keep s_to_t and t_to_s. A mismatch in either direction means the answer is false.

Complexity, mistakes and edge cases

Complexity

OperationAverageWorst case
insert, lookup, deleteO(1)O(n) with heavy collisions
iterate all keysO(n)O(n)
Counter(s)O(len(s))

Interviewers accept "O(1) average" for hash operations. If asked about the worst case, mention collisions, and that languages randomise hash seeds partly to defend against crafted inputs.

Common mistakes

Edge cases

Empty input, a single element, all elements identical, negative numbers and zero, case sensitivity in strings, and k = 0 in window questions. For anagram and frequency questions, ask whether the alphabet is only lowercase English letters; a fixed alphabet lets you use an array of size 26 and claim O(1) extra space.

Comparing frequency shapes

Some questions ask whether one string can be turned into another by swapping characters or relabelling them. The answer often depends only on two facts: both strings use the same set of characters, and the sorted list of counts is the same. Spotting that you can compare sorted(Counter(a).values()) with sorted(Counter(b).values()) is a very common "aha" moment.

Variations and practise

Common twists

How to talk through it

Say what the map stores in one sentence: "a map from value to the latest index where it appeared". If you cannot phrase it that clearly, the code will probably be muddled too.

Practise

The problems below start with direct counting and lookup, then move to grouping, bijections, and the consecutive-run trick. For each one, before writing code, name the key and the value of your map. Aim to finish the Easy ones in under ten minutes and explain your space usage on every Medium.

Practise

Easy

Medium

Hard

Practise this in the app All guides