Loading repovive.com/roadmaps/data-structures
Roadmaps
Data Structures
Binary Search Trees
Problemset
Discussion
AI Helper
Arrays & Prefix Sums
0/50
1
Intro
2
Array Fundamentals
3
The Range Sum Problem
4
Vocabulary - Prefix Sum
5
The Core Idea
6
Visualization
7
Problem - Range Sum Query
8
Range Sum - Building the Array
9
Range Sum - Answering Queries
10
Range Sum - Implementation
11
Lessons from Range Sum
12
Quiz: Prefix Sum Basics
13
Extending to 2D
14
Vocabulary - 2D Prefix Sum
15
2D Prefix - The Formula
16
2D Prefix - Building
17
Problem - 2D Range Sum
18
2D Range Sum - Build
19
2D Range Sum - Query
20
Lessons from 2D Prefix
21
Quiz: 2D Prefix Sums
22
The Range Update Problem
23
Vocabulary - Difference Array
24
Difference Array Insight
25
Difference Array Visualization
26
Problem - Range Addition
27
Range Addition - Algorithm
28
Range Addition - Implementation
29
Lessons from Difference Arrays
30
Quiz: Difference Arrays
31
The Pair Finding Problem
32
Vocabulary - Two Pointers
33
Two Pointers Logic
34
Problem - Two Sum Sorted
35
Two Sum Sorted - Why It Works
36
Two Sum Sorted - Implementation
37
Lessons from Two Pointers
38
Quiz: Two Pointers
39
The Subarray Problem
40
Vocabulary - Sliding Window
41
Fixed Window Pattern
42
Problem - Maximum Average Subarray
43
Max Average - Implementation
44
Variable Window Pattern
45
Problem - Longest Substring
46
Longest Substring - The Idea
47
Longest Substring - Implementation
48
Lessons from Sliding Window
49
Quiz: Sliding Window
50
Section Recap
Stacks & Monotonic Stacks
0/40
1
Intro
2
Vocabulary - Stack
3
Stack Visualization
4
Stack Implementation
5
Where Stacks Shine
6
The Matching Problem
7
Problem - Valid Parentheses
8
Valid Parentheses - Algorithm
9
Valid Parentheses - Implementation
10
Lessons from Valid Parentheses
11
Quiz: Stack Basics
12
A Harder Problem
13
Vocabulary - Monotonic Stack
14
Why Monotonic Works
15
Monotonic Stack Visualization
16
Problem - Next Greater Element I
17
Next Greater - Algorithm
18
Next Greater - Implementation
19
Lessons from Next Greater
20
Quiz: Monotonic Stack
21
Problem - Daily Temperatures
22
Daily Temperatures - The Idea
23
Daily Temperatures - Implementation
24
Lessons from Daily Temperatures
25
A Famous Problem
26
Histogram - Key Observation
27
Histogram - The Approach
28
Histogram - Visualization
29
Histogram - Why It Works
30
Histogram - Implementation
31
Lessons from Histogram
32
Quiz: Histogram
33
Monotonic Stack Variants
34
Previous vs Next
35
Recognizing Stack Problems
36
Problem - Trapping Rain Water
37
Trapping Water - Stack Approach
38
Trapping Water - Implementation
39
Quiz: Stack Problem Types
40
Section Recap
Queues & Deques
0/38
1
Intro
2
Vocabulary - Queue
3
Queue Visualization
4
Queue Implementation
5
Where Queues Shine
6
BFS Overview
7
Problem - Number of Recent Calls
8
Recent Calls - Algorithm
9
Recent Calls - Implementation
10
Lessons from Recent Calls
11
Quiz: Queue Basics
12
The Limitation of Queues
13
Vocabulary - Deque
14
Deque Implementation
15
The Sliding Window Maximum
16
Vocabulary - Monotonic Deque
17
Why Monotonic Deque Works
18
Monotonic Deque Visualization
19
Problem - Sliding Window Maximum
20
Sliding Max - Algorithm
21
Sliding Max - Implementation
22
Lessons from Sliding Max
23
Quiz: Monotonic Deque
24
Sliding Window Minimum
25
A Harder Problem
26
Shortest Subarray - The Idea
27
Shortest Subarray - Algorithm
28
Shortest Subarray - Implementation
29
Lessons from Shortest Subarray
30
Quiz: Deque vs Stack vs Queue
31
Deque vs Two Stacks
32
When to Use Deques
33
Problem - Constrained Subsequence Sum
34
Constrained Sum - DP Formulation
35
Constrained Sum - Implementation
36
Lessons from Constrained Sum
37
Quiz: DP Optimization
38
Section Recap
Hash Tables
0/40
1
Intro
2
Vocabulary - Hash Table
3
How Hashing Works
4
Hash Table Operations
5
Hash Set vs Hash Map
6
Pattern - Frequency Counting
7
Frequency Counting Applications
8
Problem - Valid Anagram
9
Valid Anagram - Algorithm
10
Valid Anagram - Implementation
11
Lessons from Valid Anagram
12
Quiz: Frequency Counting
13
The Pair Finding Problem
14
Pattern - Complement Lookup
15
Problem - Two Sum
16
Two Sum - Algorithm
17
Two Sum - Implementation
18
Lessons from Two Sum
19
Quiz: Two Sum Pattern
20
Problem - Group Anagrams
21
Group Anagrams - Key Design
22
Group Anagrams - Implementation
23
Lessons from Group Anagrams
24
Combining Techniques
25
The Core Idea
26
Problem - Subarray Sum Equals K
27
Subarray Sum - Algorithm
28
Subarray Sum - Why Initialize with 0
29
Subarray Sum - Implementation
30
Lessons from Subarray Sum
31
Quiz: Prefix Sum + Hash
32
A Harder Problem
33
Longest Consecutive - The Idea
34
Longest Consecutive - Algorithm
35
Longest Consecutive - Implementation
36
Lessons from Longest Consecutive
37
Quiz: Hash Set Usage
38
When Hashing Fails
39
Recognizing Hash Problems
40
Section Recap
Heaps & Priority Queues
0/43
1
Intro
2
Vocabulary - Heap
3
Heap Visualization
4
Array Representation
5
Heap Operations Overview
6
Insert Operation
7
Extract Operation
8
Bubble Down Details
9
Vocabulary - Priority Queue
10
Using Built-in Heaps
11
Quiz: Heap Basics
12
Problem - Last Stone Weight
13
Last Stone - Algorithm
14
Last Stone - Implementation
15
Lessons from Last Stone
16
The K-th Element Problem
17
K-th Largest with Min-Heap
18
Problem - Kth Largest Element
19
Kth Largest - Algorithm
20
Kth Largest - Implementation
21
Lessons from Kth Largest
22
Quiz: K-th Element
23
Problem - Top K Frequent Elements
24
Top K Frequent - Algorithm
25
Top K Frequent - Implementation
26
Lessons from Top K Frequent
27
The Merge Problem
28
K-Way Merge with Heap
29
Problem - Merge K Sorted Lists
30
Merge K Lists - Implementation
31
Lessons from Merge K Lists
32
Quiz: K-Way Merge
33
The Median Problem
34
Two Heaps Technique
35
Two Heaps Visualization
36
Problem - Find Median from Data Stream
37
Median Stream - Invariants
38
Median Stream - Implementation
39
Lessons from Median Stream
40
Quiz: Two Heaps
41
When to Use Heaps
42
Heap vs Sorting
43
Section Recap
Linked Lists
0/36
1
Intro
2
Node Structure
3
Traversal Pattern
4
Dummy Head Technique
5
Insertion Operations
6
Deletion Operations
7
Problem - Reverse Linked List
8
Iterative Reversal
9
Recursive Reversal
10
Reverse Linked List Solution
11
Fast-Slow Pointer Technique
12
Finding the Middle
13
Problem - Linked List Cycle
14
Cycle Detection with Fast-Slow
15
Linked List Cycle Solution
16
Finding Cycle Start
17
Problem - Merge Two Sorted Lists
18
Merge with Dummy Head
19
Merge Two Sorted Lists Solution
20
Doubly Linked Lists
21
DLL Insertion
22
Problem - LRU Cache
23
LRU Cache Design
24
LRU Helper Methods
25
LRU Cache Solution
26
Reverse Sublist
27
Reverse in Groups
28
Problem - Reorder List
29
Reorder List Approach
30
Reorder List Solution
31
Problem - Copy List with Random
32
Hash Map Approach
33
Interleaving Approach
34
Copy List Solution
35
Quiz: Linked Lists
36
Section Recap
Binary Trees
0/35
1
Intro
2
Binary Tree Node
3
Tree Properties
4
Three Traversal Orders
5
Recursive Traversal
6
Problem - Binary Tree Inorder
7
Iterative Inorder
8
Inorder Traversal Solution
9
Level Order Traversal
10
Recursive Tree Thinking
11
Problem - Maximum Depth
12
Max Depth Solution
13
Problem - Same Tree
14
Same Tree Solution
15
Problem - Invert Binary Tree
16
Invert Tree Solution
17
Problem - Symmetric Tree
18
Symmetric Tree Solution
19
Path Sum Pattern
20
Problem - Path Sum
21
Path Sum Solution
22
Building Trees from Traversals
23
Problem - Construct from Traversals
24
Construction Algorithm
25
Construct Tree Solution
26
Lowest Common Ancestor
27
Serialization Pattern
28
Problem - Diameter of Binary Tree
29
Diameter Solution
30
Problem - Flatten to Linked List
31
Flatten Solution
32
Morris Traversal
33
Binary Tree from Array
34
Quiz: Binary Trees
35
Section Recap
Binary Search Trees
0/35
1
Intro
2
BST Property
3
Inorder Gives Sorted Order
4
BST Search
5
BST Insertion
6
BST Deletion
7
Problem - Validate BST
8
Validate BST: Range Approach
9
Validate BST Solution
10
Problem - Search in BST
11
Search in BST Solution
12
Problem - Insert into BST
13
Insert into BST Solution
14
Problem - Delete Node in BST
15
Delete Node: Finding Successor
16
Delete Node in BST Solution
17
Problem - Kth Smallest Element
18
Kth Smallest Solution
19
Problem - LCA of BST
20
LCA of BST Solution
21
Why Balance Matters
22
AVL Tree Concept
23
When to Use BSTs
24
Problem - Sorted Array to BST
25
Sorted Array to BST Solution
26
Problem - BST Iterator
27
BST Iterator Solution
28
Problem - Recover BST
29
Recover BST: Finding Violations
30
Recover BST Solution
31
Floor and Ceiling
32
BST from Preorder
33
Successor and Predecessor
34
Quiz: Binary Search Trees
35
Section Recap
Tries
0/35
1
Intro
2
Trie Node Structure
3
Trie Insert Operation
4
Trie Search Operation
5
Prefix Search
6
Problem - Implement Trie
7
Trie Implementation
8
Implement Trie Solution
9
Counting Words with Prefix
10
Trie Deletion
11
Problem - Add and Search Word
12
Wildcard Search Strategy
13
Add and Search Solution
14
Problem - Word Search II
15
Word Search II: Trie Approach
16
Word Search II Optimizations
17
Word Search II Solution
18
Problem - Longest Word in Dictionary
19
Longest Word Solution
20
Compressed Tries (Radix Trees)
21
Suffix Tries and Suffix Trees
22
Problem - Maximum XOR of Two Numbers
23
Bitwise Trie Concept
24
Maximum XOR Solution
25
Problem - Search Autocomplete
26
Autocomplete Design
27
Autocomplete Solution
28
Problem - Replace Words
29
Replace Words Solution
30
Array vs Map Children
31
Trie Memory Optimization
32
Trie vs Hash Set
33
Counting Distinct Substrings
34
Quiz: Tries
35
Section Recap
Union-Find
0/35
1
Intro
2
Basic Structure
3
Basic Union
4
Path Compression
5
Union by Rank
6
Union by Size
7
Complexity Analysis
8
Problem - Number of Connected Components
9
Connected Components Solution
10
Problem - Redundant Connection
11
Cycle Detection with Union-Find
12
Problem - Number of Provinces
13
Provinces Solution
14
Problem - Graph Valid Tree
15
Valid Tree Solution
16
Weighted Union-Find
17
Problem - Evaluate Division
18
Evaluate Division: Weighted UF
19
Evaluate Division Solution
20
Problem - Accounts Merge
21
Accounts Merge Approach
22
Accounts Merge Solution
23
Problem - Largest Component Size by Factor
24
Union by Prime Factors
25
Largest Component Solution
26
Problem - Swimming in Rising Water
27
Swimming Solution
28
Kruskal's Algorithm
29
Problem - Min Cost to Connect Points
30
Min Cost Solution
31
Union-Find with Rollback
32
Online vs Offline Problems
33
Common Union-Find Bugs
34
Quiz: Union-Find
35
Section Recap
Segment Trees
0/35
1
Intro
2
Segment Tree Structure
3
Array Representation
4
Building the Tree
5
Range Query
6
Point Update
7
Problem - Range Sum Query Mutable
8
Segment Tree Implementation
9
Range Sum Query Solution
10
Range Minimum Query
11
Segment Tree Generalization
12
The Range Update Problem
13
Lazy Propagation Structure
14
Push Down Operation
15
Range Update with Lazy
16
Query with Lazy
17
Problem - Range Addition
18
Range Addition Solution
19
Range Set Operation
20
Problem - Count of Range Sum
21
Count Range Sum Approach
22
Count Range Sum Solution
23
Iterative Segment Tree
24
Iterative Query and Update
25
Problem - Count Smaller After Self
26
Count Smaller Solution
27
2D Segment Trees
28
Problem - Range Sum Query 2D Mutable
29
2D Segment Tree Solution
30
Persistent Segment Trees
31
Dynamic Segment Trees
32
Segment Tree vs BIT
33
Common Segment Tree Bugs
34
Quiz: Segment Trees
35
Section Recap
Fenwick Trees
0/35
1
Intro
2
The Core Idea
3
Lowest Set Bit
4
Fenwick Tree Structure
5
Prefix Sum Query
6
Point Update
7
Building a Fenwick Tree
8
Problem - Range Sum Query Mutable
9
BIT Implementation
10
Range Sum BIT Solution
11
Range Update Point Query
12
Range Update Range Query
13
Problem - Count Inversions
14
Inversions with BIT
15
Count Inversions Solution
16
2D Fenwick Tree
17
2D Range Sum Query
18
Problem - Range Sum Query 2D Mutable
19
2D BIT Solution
20
Order Statistics with BIT
21
BIT for Offline Queries
22
Problem - Count Smaller After Self
23
Count Smaller BIT Solution
24
Problem - Reverse Pairs
25
Reverse Pairs Solution
26
BIT vs Segment Tree
27
BIT for XOR Queries
28
Finding First Position
29
Dynamic Frequency Queries
30
Problem - Global and Local Inversions
31
Global Local Solution
32
Common BIT Mistakes
33
Challenge: Implement Your Own
34
Quiz: Fenwick Trees
35
Section Recap
Sparse Tables
0/35
1
Intro
2
Power-of-2 Ranges
3
Building the Table
4
The Overlap Trick
5
Precomputing Log Values
6
Problem - Range Minimum Query
7
Sparse Table RMQ Solution
8
RMQ Solution
9
Idempotent Operations
10
Non-Idempotent Queries
11
Problem - Range GCD Queries
12
Range GCD Solution
13
LCA with Sparse Table
14
Euler Tour Construction
15
Problem - LCA Queries
16
LCA Solution
17
Range Max with Index
18
2D Sparse Table
19
Sparse Table vs Others
20
Problem - Static Range Min
21
Static RMQ Solution
22
Second Minimum Query
23
Min with Index
24
Disjoint Sparse Tables
25
Sparse Table for Matrices
26
Problem - Range Xor Queries
27
Range XOR Solution
28
Problem - Forest Queries
29
Forest Queries Solution
30
Common Sparse Table Mistakes
31
Space Optimization
32
RMQ to LCA Reduction
33
Challenge: Multiple Values
34
Quiz: Sparse Tables
35
Section Recap
Sqrt Decomposition
0/42
1
Intro
2
The Core Idea
3
Vocabulary - Block Size
4
Quiz: Block Index
5
Building Block Sums
6
Range Sum Query
7
Range Sum - Implementation
8
Point Updates
9
Point Update - Implementation
10
Problem - Range Sum Queries I
11
Range Sum I - Analysis
12
Range Sum I - Implementation
13
Lessons from Range Sum
14
Range Minimum Query
15
Range Min - Update Challenge
16
Quiz: Update Complexity
17
When to Use Sqrt Decomposition
18
MO's Algorithm - Introduction
19
MO's Sorting Order
20
MO's Algorithm - Framework
21
Problem - Distinct Values
22
Distinct Values - Add/Remove
23
Distinct Values - Implementation
24
Lessons from Distinct Values
25
MO's with Expensive Operations
26
Problem - Mode Query
27
Mode Query - Data Structures
28
Mode Query - Implementation
29
Lessons from Mode Query
30
MO's Optimization - Zigzag Order
31
Quiz: MO's Complexity
32
Block Decomposition for Updates
33
Lazy Block Updates
34
Problem - Polynomial Queries
35
Polynomial Queries - Analysis
36
Polynomial Queries - Pushdown
37
Lessons from Polynomial Queries
38
MO's with Updates
39
MO's with Updates - Analysis
40
Comparing Sqrt to Other Structures
41
Challenge: Design Your Solution
42
Section Recap
Advanced Trees
0/42
1
Intro
2
Heavy-Light Decomposition
3
Heavy vs Light Edges
4
Quiz: Light Edge Bound
5
Building Heavy Chains
6
HLD Construction - Code
7
Path Queries with HLD
8
HLD Path Query - Code
9
Problem - Path Queries
10
Path Queries - Analysis
11
Path Queries - Implementation
12
Lessons from Path Queries
13
Centroid Decomposition
14
Finding the Centroid
15
Centroid Finding - Code
16
Quiz: Centroid Property
17
Centroid Decomposition - Structure
18
Centroid Decomposition - Code
19
Problem - Distance Queries
20
Distance Queries - Analysis
21
Distance Queries - Implementation
22
Lessons from Distance Queries
23
Treaps - Introduction
24
Treap Properties
25
Quiz: Treap Structure
26
Treap Operations - Split
27
Treap Operations - Merge
28
Treap Insert and Delete
29
Implicit Treaps
30
Implicit Treap - Split by Size
31
Problem - Cut and Paste
32
Cut and Paste - Analysis
33
Cut and Paste - Implementation
34
Lessons from Cut and Paste
35
Euler Tour Technique
36
Euler Tour - Construction
37
Subtree Queries with Euler Tour
38
HLD vs Euler Tour vs Centroid
39
Problem - Subtree Queries
40
Subtree Queries - Implementation
41
Challenge: Combined Techniques
42
Section Recap
Interval Trees
0/40
1
Intro
2
Interval Representation
3
The Overlap Problem
4
Interval Tree Structure
5
Building the Tree
6
Point Query
7
Why Dual Sorting Works
8
Problem - Merge Intervals
9
Merge Intervals: Sorting Approach
10
Merge Intervals Solution
11
Problem - Insert Interval
12
Insert Interval Approach
13
Insert Interval Solution
14
Augmented BST Approach
15
Maintaining maxHigh
16
Overlap Search in Augmented BST
17
Finding All Overlaps
18
Problem - Meeting Rooms
19
Meeting Rooms Solution
20
Problem - Meeting Rooms II
21
Meeting Rooms II: Event Sweep
22
Meeting Rooms II: Heap Approach
23
Meeting Rooms II Solution
24
Problem - Range Module
25
Range Module: TreeMap Approach
26
Range Module Solution
27
Interval Scheduling Maximization
28
Problem - Non-overlapping Intervals
29
Non-overlapping Solution
30
Segment Tree for Intervals
31
Coordinate Compression
32
2D Interval Problems
33
Problem - Rectangle Area II
34
Rectangle Area: Sweep Line
35
Rectangle Area II Solution
36
Interval Tree vs Segment Tree
37
Stabbing Number Problem
38
Interval Partitioning
39
Quiz: Interval Trees
40
Section Recap
Wavelet Trees
0/37
1
Intro
2
The Range Counting Problem
3
Binary Representation Insight
4
Wavelet Tree Structure
5
Building the Wavelet Tree
6
Example: Building Step by Step
7
Bitvector Rank Operation
8
Efficient Rank with Prefix Sums
9
Position Mapping
10
Count of Value in Range
11
Range Count by Value Range
12
Problem - Range Frequency Query
13
Range Frequency: Hash Map Approach
14
Range Frequency Solution
15
K-th Smallest in Range
16
K-th Smallest: Why It Works
17
Problem - Kth Smallest in Range
18
Kth Smallest: Merge Sort Tree
19
Wavelet vs Merge Sort Tree
20
Count Less Than in Range
21
Count Greater Than in Range
22
Successor in Range
23
Problem - Count Smaller After Self
24
Count Smaller: Multiple Approaches
25
Count Smaller Solution
26
Space Optimization
27
Coordinate Compression
28
Dynamic Wavelet Trees
29
Wavelet Matrix
30
Wavelet Matrix Operations
31
Application: Mode in Range
32
Application: Range Majority
33
Application: Distinct Count
34
Implementation Tips
35
Common Bugs
36
Quiz: Wavelet Trees
37
Section Recap
Link-Cut Trees
0/39
1
Intro
2
Dynamic Tree Problems
3
Operations We Need
4
Splay Tree Review
5
Rotations
6
Preferred Paths
7
Auxiliary Trees
8
Path-Parent Pointer
9
The Access Operation
10
Access: Step by Step
11
FindRoot Operation
12
Link Operation
13
Cut Operation
14
MakeRoot Operation
15
Why Rerooting Works
16
Path Query
17
Path Update
18
LCA Query
19
Connected Query
20
Node Structure
21
Splay with Push Down
22
Rotate with Update
23
Example: Building a Tree
24
Example: Cut and Reconnect
25
Application: Dynamic MST
26
Application: Max Flow
27
Application: Online LCA
28
Problem - Dynamic Connectivity
29
Dynamic Connectivity Solution
30
Problem - Dynamic Path Queries
31
Dynamic Path Solution
32
Amortized Analysis
33
Space Complexity
34
Implementation Tips
35
Common Bugs
36
Euler Tour Trees
37
Top Trees
38
Quiz: Link-Cut Trees
39
Section Recap
Persistent Data Structures
0/37
1
Intro
2
Types of Persistence
3
The Path Copying Technique
4
Sharing Unchanged Subtrees
5
Persistent Array
6
Persistent Array Implementation
7
Query and Update Functions
8
Persistent Segment Tree
9
Range Query on Version
10
Problem - Kth Number in Range
11
Kth Number: The Idea
12
Kth Number: Implementation
13
Kth Number: Building
14
Problem - Count in Range
15
Count in Range Solution
16
The Fat Node Method
17
Persistent Union-Find
18
Persistent UF Applications
19
Persistent Treap
20
Persistent Treap Operations
21
Problem - Version Queries
22
Version Queries Solution
23
Copy-on-Write Semantics
24
Functional Data Structures
25
Persistent Rope
26
Space Optimization
27
Memory Analysis
28
Full Persistence
29
Version Trees
30
Application: Undo/Redo
31
Application: Git-like VCS
32
Application: Database Snapshots
33
Implementation Tips
34
Common Bugs
35
Persistence vs Rollback
36
Quiz: Persistent Data Structures
37
Section Recap