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 ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEArrays + Hashing

Click anywhere 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.

Frequency Counting

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

Common Problems

• Valid Anagram
• Majority Element
• Top K Frequent Elements
• Ransom Note
• Find All Anagrams in a String

5 problems

Index Mapping

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

Common Problems

• Two Sum
• Isomorphic Strings
• Word Pattern
• Longest Substring Without Repeating Characters
• Contiguous Array

5 problems

Set Lookup

Only existence matters — no counts, no positions.

Common Problems

• Contains Duplicate
• Longest Consecutive Sequence
• Happy Number
• Intersection of Two Arrays
• Find the Duplicate Number

5 problems

In-place Marking

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

Common Problems

• Missing Number
• Find All Numbers Disappeared in an Array
• Find All Duplicates in an Array
• Set Mismatch
• First Missing Positive

5 problems

Prefix Hashing

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

Common Problems

• Subarray Sum Equals K
• Continuous Subarray Sum
• Contiguous Array
• Subarray Sums Divisible by K
• Maximum Size Subarray Sum Equals k

5 problems

Encoding / Hash Key

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

Common Problems

• Group Anagrams
• Group Shifted Strings
• Design Underground System
• Find Duplicate File in System
• Encode and Decode Strings

5 problems

Template / Approach

Template for: Frequency Counting

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_cpp

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

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}

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.

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Easy

Valid Anagram

LeetCode #242

Easy

Ransom Note

LeetCode #383

Easy

Majority Element

LeetCode #169

Medium

Top K Frequent Elements

LeetCode #347

Medium

Sort Characters By Frequency

LeetCode #451

Easy

Two Sum

LeetCode #1

Easy

Isomorphic Strings

LeetCode #205

Easy

Word Pattern

LeetCode #290

Medium

Contiguous Array

LeetCode #525

Easy

Contains Duplicate

LeetCode #217

Easy

Happy Number

LeetCode #202

Medium

Longest Consecutive Sequence

LeetCode #128

Easy

Intersection of Two Arrays

LeetCode #349

Easy

Missing Number

LeetCode #268

Easy

Find All Numbers Disappeared in an Array

LeetCode #448

Medium

Find All Duplicates in an Array

LeetCode #442

Hard

First Missing Positive

LeetCode #41

Easy

Set Mismatch

LeetCode #645

Medium

Subarray Sum Equals K

LeetCode #560

Medium

Subarray Sums Divisible by K

LeetCode #974

Medium

Continuous Subarray Sum

LeetCode #523

Medium

Maximum Size Subarray Sum Equals k

LeetCode #325

Medium

Group Anagrams

LeetCode #49

Medium

Group Shifted Strings

LeetCode #249

Medium

Find Duplicate File in System

LeetCode #609

1// ── Step 1: build frequency map ─────────────────

2unordered_map<int, int> freq;

4for (auto x : nums)

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}