Cheatsheet›Arrays + Hashing

CORE PATTERNVery High Frequency

Arrays + Hashing

Store information while scanning the array so you can answer questions in O(1) instead of repeatedly searching. A single pass builds the map; a second pass (or the same pass) queries it.

TimeO(N)

SpaceO(N)

DifficultyEasy to Medium

Key Insight

Remember the past to solve the present.

Flip ⟲

Hash MapO(1) lookup

—

key:1

—

hash(1) → bucket 1

FLIP SIDEArrays + Hashing

Tap to flip back ⟲

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

✓Count occurrences or frequencies

✓Need the index where something was previously seen

✓Only existence / membership check matters

✓Numbers are in the range 1…n (in-place marking possible)

✓Subarray sum, XOR, or modulo equals a target

✓Group or bucket elements by a shared property

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

✓ SELECTED

Frequency Counting

Count how many times each element appears, then query those counts.

Valid Anagram
Majority Element
Top K Frequent Elements

5 problems

Index Mapping

Store where you saw a value so you can look it up in O(1) later.

Two Sum
Isomorphic Strings
Word Pattern

5 problems

Set Lookup

Only existence matters — no counts, no positions.

Contains Duplicate
Longest Consecutive Sequence
Happy Number

5 problems

In-place Marking

Use the array itself as the hash table — O(1) extra space.

Missing Number
Find All Numbers Disappeared in an Array
Find All Duplicates in an Array

5 problems

Prefix Hashing

Hash the running prefix sum to find subarrays with a target sum in O(N).

Subarray Sum Equals K
Continuous Subarray Sum
Contiguous Array

5 problems

Encoding / Hash Key

Convert complex objects into one canonical string key to bucket equivalents together.

Group Anagrams
Group Shifted Strings
Design Underground System

5 problems

Template / Approach

Template for: Frequency Counting

Approach

Initialize Map

Declare an unordered_map<T, int> to store element → count pairs.

Count Items

Loop through the input and do freq[x]++ for every element x.

Process Counts

Iterate the frequency map or query it directly to decide the answer.

Template

</>Common Template

💡Universal frequency-count skeleton. Build the map in one pass, then use the counts in a second pass or inline query.

🔑

Key Idea:Store Value → Count. Two passes are common: build frequency first, then use frequency. For fixed alphabets (26 chars) use a plain int array instead of a map.

1// ── Step 1: build frequency map ─────────────────
2unordered_map<int, int> freq;
3 
4for (auto x : nums)
5{
6    freq[x]++;
7}
8 
9// ── Step 2: query / process counts ──────────────
10for (auto& [val, cnt] : freq)
11{
12    // val → element value
13    // cnt → number of occurrences
14 
15    if (cnt > 1)  { /* duplicate */ }
16    if (cnt == 1) { /* unique    */ }
17}

6 freq[x]++;

9// ── Step 2: query / process counts ──────────────

10for (auto& [val, cnt] : freq)

11{

12 // val → element value

13 // cnt → number of occurrences

15 if (cnt > 1) { /* duplicate */ }

16 if (cnt == 1) { /* unique */ }

17}

Arrays + Hashing

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

Frequency Counting

Index Mapping

Set Lookup

In-place Marking

Prefix Hashing

Encoding / Hash Key

Template / Approach

Approach

Initialize Map

Count Items

Process Counts

Template

Practice Problems

Valid Anagram

Ransom Note

Majority Element

Top K Frequent Elements

Sort Characters By Frequency

Two Sum

Isomorphic Strings

Word Pattern

Contiguous Array

Contains Duplicate

Happy Number

Longest Consecutive Sequence

Intersection of Two Arrays

Missing Number

Find All Numbers Disappeared in an Array

Find All Duplicates in an Array

First Missing Positive

Set Mismatch

Subarray Sum Equals K

Subarray Sums Divisible by K

Continuous Subarray Sum

Maximum Size Subarray Sum Equals k

Group Anagrams

Group Shifted Strings

Find Duplicate File in System

Arrays + Hashing

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

Frequency Counting

Index Mapping

Set Lookup

In-place Marking

Prefix Hashing

Encoding / Hash Key

Template / Approach

Approach

Initialize Map

Count Items

Process Counts

Template

Practice Problems

Valid Anagram

Ransom Note

Majority Element

Top K Frequent Elements

Sort Characters By Frequency

Two Sum

Isomorphic Strings

Word Pattern

Contiguous Array

Contains Duplicate

Happy Number

Longest Consecutive Sequence

Intersection of Two Arrays

Missing Number

Find All Numbers Disappeared in an Array

Find All Duplicates in an Array

First Missing Positive

Set Mismatch

Subarray Sum Equals K

Subarray Sums Divisible by K

Continuous Subarray Sum

Maximum Size Subarray Sum Equals k

Group Anagrams