patternDSA/Hash Maps

Core Pattern → Pattern 05

Hash Maps

Trade memory for speed. Turn O(n) searches into O(1) lookups. The single most versatile data structure in interview problems.

Frequency:★★★★★

·~35 min·Beginner·5 problems

←Prefix Sum

The Core Shock

"Does this value exist?" — O(n) scan vs O(1) lookup

Linear Scan (Array/Set naive)

O(n) per query

n=1,000,000: up to 1M comparisons each lookup

O(n)

HashMap Lookup

O(1) per query

n=1,000,000: exactly 1 hash + 1 comparison

O(1) avg

The insight: a hash function maps any key to an integer index in O(1). Python's dict gives you a lookup table where key in d and d[key] are both O(1). Use this to eliminate inner loops entirely.

The Two HashMap Patterns

Every HashMap problem uses one of these two patterns. Identify which before writing code.

Index Map (value → index)

Store a value and where you've seen it. At each step, check if the complement/partner already exists in the map. Enables O(1) 'have I seen X before?' queries.

Test: Ask: 'Do I need to remember where I saw a value?' If yes → index map.

Two SumSubarray Sum = KLongest Consecutive SequenceContains Duplicate II

Frequency Counter (value → count)

Store a value and how many times you've seen it. Use frequencies to check anagrams, find unique chars, build palindromes, count occurrences.

Test: Ask: 'Do I need to know how many times each value appears?' If yes → frequency counter.

First Non-Repeating CharValid AnagramLongest PalindromeGroup AnagramsRansom Note

The 3-Step HashMap Framework

The same three steps work for every HashMap problem.

Choose Your Map Type + Initialize

Decide: index map (value → index) or frequency counter (value → count)? Initialize an empty dict or Counter before any loop.

seen = {}          # index map
freq = Counter(s)  # frequency counter

The choice of map type is the entire solution strategy. Get this right first and the rest follows.

Query Before Storing

For index maps: check if the complement exists BEFORE storing the current element. This avoids matching an element with itself and ensures correct index pairs.

if complement in seen:   # query first
    return [seen[complement], i]
seen[num] = i          # then store

Order matters: query → process → store. Storing before querying can match an element with itself (num + num = target when num = target/2).

Read + Analyze the Map

For frequency counters: after building the map, make a second pass to analyze it. Count chars with even/odd frequency, find the first unique, compare two maps.

for ch, count in freq.items():
    if count % 2 == 0:
        result += count

Two passes is standard and perfectly O(n). Building the map is pass 1. Using the map is pass 2.

Pattern Recognition

30-second diagnosis: does this need a HashMap?

Use HashMap When

"Two elements that sum to target"

Need to detect duplicates efficiently

"First/last occurrence of X"

Counting frequencies of elements

"Group by some property"

Nested loop is O(n²) — need O(n)

"Does complement/pair exist?"

Any "has seen before" question

Do NOT Use HashMap When

Sorted array — use Binary Search instead

Need index-based access — use array

Contiguous subarray — use Sliding Window

Only two elements — use Two Pointers

Problem is already O(n), map adds no speedup

Order matters and must be preserved (use OrderedDict)

On this page