Arrays & Hashing Pattern

All lessons

Learn when an array scan should carry a set, map, or reusable prefix state—and when another pattern is the better choice.

0/5 practice problems solved

Skip to practice

Recognizing the pattern

Reach for it when you need to

detect a value seen before;
count, group, or compare frequencies;
find a complement during one pass;
reuse prefix information instead of rescanning.

Don't use it when

Contiguous ranges may need a sliding window.
Sorted input may favor two pointers or binary search.
Nested choices may need dynamic programming or backtracking.
Strict O(1) space rules out an auxiliary map unless values are bounded.

Core mental model

Scan once and keep only past information that answers a future question. Before index i, the map or set summarizes exactly the processed prefix; after processing it, the same invariant holds for the next index.

Typical time: O(n)

Typical space: O(n)

Sorting alternative: O(n log n)

Visual trace

Two Sum, target 9. Check the complement in `seen` before storing the current value.

Index 0: store 2 — seen is empty, so 2 has no complement yet.

Index 1: complement found — seen has {2: 0}; nums[1] = 7, and 9 - 7 = 2 is already in seen.

Scroll the diagrams sideways to see all of them.

Worked example: Two Sum

Input [2, 7, 11, 15], target 9. Check the complement before storing the current value.

Step-by-step trace of Two Sum
Index/value	Needed	Seen	Decision
0 / 2	7	{}	Store 2 → 0
Key step: 1 / 7	2	{2: 0}	Found; return [0, 1]

Invariant: seen contains exactly the values before i, so one item cannot be used twice.

Reusable template

The shape to adapt for a new problem in this pattern.

python

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

Common mistakes

Storing before checking and reusing the current item.
Using a set when the answer needs an index or count.
Overwriting duplicate information too early.
Calling O(n) map storage O(1) space.
Assuming hashing is ordered or worst-case constant time.

Practice: easy → medium → timed check

Solve in order; each step adds one decision to the same pattern.

1. Contains Duplicate
Easy
Not solved yet
Set membership
Solution for Contains Duplicate Practice Contains Duplicate
2. Valid Anagram
Easy
Not solved yet
Frequency counting
Solution for Valid Anagram Practice Valid Anagram
3. Two Sum
Easy
Not solved yet
Complement lookup
Solution for Two Sum Practice Two Sum
4. Product of Array Except Self
Medium
Not solved yet
Prefix and suffix state
Solution for Product of Array Except Self Practice Product of Array Except Self
5. Top K Frequent Elements
Medium
Not solved yet
Count, then rank
Solution for Top K Frequent Elements Practice Top K Frequent Elements

Final timed check

Run a 30-minute mock covering this pattern; state the invariant before coding, then finish with complexity and edge cases.

Start timed mock

Next lesson

Two Pointers

Continue