Loading repovive.com/roadmaps/graph-problem-solving
Roadmaps
Graph: Problem Solving
Premium
Grid Graphs
Problemset
Discussion
AI Helper
Getting Started
0/4
1
Intro
2
Who This Is For
3
What You'll Learn
4
How to Use This Roadmap
Shortest Path Variants
0/30
1
Introduction to Shortest Path Variants
2
What Shortest Path Variants Solve
3
When to Use Each Algorithm
4
State-Space BFS Pattern
5
Problem - Grid with Obstacles Elimination
6
Grid with Obstacles Elimination - Why Naive Fails
7
Grid with Obstacles Elimination - Defining the DP
8
Grid with Obstacles Elimination - Transition
9
Grid with Obstacles Elimination - Base Cases
10
Grid with Obstacles Elimination - Implementation
11
Grid with Obstacles Elimination - Time and Space
12
0-1 BFS - The Deque Trick
13
Min Cost Valid Path - Why 0-1 BFS?
14
Ways to Arrive - Counting Shortest Paths
15
Problem - Min Cost Valid Path
16
Min Cost Valid Path - Solution
17
Problem - Ways to Arrive
18
Ways to Arrive - Solution
19
Quiz: Pattern Recognition
20
Quiz: Edge Cases
21
Common Mistakes in Shortest Path
22
Problem - Reachable Nodes In Subdivided Graph
23
Reachable Nodes In Subdivided Graph - Solution
24
Problem - Shortest Path with Alternating Colors
25
Shortest Path with Alternating Colors - Solution
26
Problem - Shortest Path Visiting All Nodes
27
Shortest Path Visiting All Nodes - Solution
28
Problem - Minimum Weighted Subgraph
29
Minimum Weighted Subgraph - Solution
30
Section Recap
Grid Graphs
0/33
1
Introduction to Grid Graphs
2
What Grid Problems Solve
3
When to Use Grid Techniques
4
Multi-Source BFS Pattern
5
Problem - Get All Keys
6
Get All Keys - Why Naive Fails
7
Get All Keys - Defining the State
8
Get All Keys - Transition
9
Get All Keys - Base Cases
10
Get All Keys - Implementation
11
Get All Keys - Time and Space
12
Problem - Pacific Atlantic
13
Pacific Atlantic - Why Naive Fails
14
Pacific Atlantic - Defining the Approach
15
Pacific Atlantic - Core Logic
16
Pacific Atlantic - Implementation
17
Problem - Surrounded Regions
18
Surrounded Regions - Why Naive Fails
19
Surrounded Regions - Defining the Approach
20
Surrounded Regions - Core Logic
21
Surrounded Regions - Implementation
22
Boundary DFS Pattern
23
Problem - Shortest Bridge
24
Shortest Bridge - Solution
25
Shortest Bridge - Why This Works
26
Quiz: Grid Pattern Recognition
27
Quiz: Boundary Techniques
28
Common Mistakes in Grid Graphs
29
Problem - Minimum Moves with Rotations
30
Minimum Moves with Rotations - Solution
31
Problem - Escape the Spreading Fire
32
Escape the Spreading Fire - Solution
33
Section Recap
Connectivity (DSU and DFS)
0/27
1
Introduction to Connectivity
2
Union-Find with Path Compression and Rank
3
DSU vs DFS
4
Problem - Number of Islands II
5
Number of Islands II - Why Naive Fails
6
Number of Islands II - Setting Up Union-Find
7
Number of Islands II - Transition
8
Number of Islands II - Base Cases
9
Number of Islands II - Implementation
10
Number of Islands II - Time and Space
11
Problem - Graph Valid Tree
12
Graph Valid Tree - Solution
13
Graph Valid Tree - Why This Works
14
Quiz: Union-Find Applications
15
Quiz: Cycle Detection
16
Common Mistakes in Connectivity
17
Problem - New Roads Queries
18
New Roads Queries - Solution
19
Problem - Number of Good Paths
20
Number of Good Paths - Solution
21
Problem - Rank Transform of Matrix
22
Rank Transform of Matrix - Solution
23
Problem - Asya and Kittens
24
Asya and Kittens - Solution
25
Problem - Cows and Snacks
26
Cows and Snacks - Solution
27
Section Recap
DAG and Topological Sort
0/28
1
Introduction to DAGs and Topological Sort
2
What DAG Problems Solve
3
When to Use Topological Sort
4
Kahn's vs DFS Topological Sort
5
Problem - Alien Dictionary
6
Alien Dictionary - Why Naive Fails
7
Alien Dictionary - Building the Graph
8
Alien Dictionary - Transition
9
Alien Dictionary - Base Cases
10
Alien Dictionary - Implementation
11
Alien Dictionary - Time and Space
12
Problem - Longest Increasing Path
13
Longest Increasing Path - Why Naive Fails
14
Longest Increasing Path - Defining the DP
15
Longest Increasing Path - Core Logic
16
Longest Increasing Path - Implementation
17
DP on DAG Pattern
18
Problem - Find All Recipes
19
Find All Recipes - Solution
20
Find All Recipes - Why This Works
21
Problem - Parallel Courses
22
Parallel Courses - Solution
23
Quiz: Topological Sort Applications
24
Quiz: DAG Properties
25
Common Mistakes in DAG Problems
26
Problem - Largest Color Value
27
Largest Color Value - Solution
28
Section Recap
Tree Algorithms
0/39
1
Introduction to Tree Algorithms
2
What Tree Problems Solve
3
Problem - Possible Root Nodes
4
Possible Root Nodes - Why Naive Fails
5
Possible Root Nodes - Defining the DP
6
Possible Root Nodes - Transition
7
Possible Root Nodes - Base Cases
8
Possible Root Nodes - Implementation
9
Rerooting DP Template
10
Possible Root Nodes - Time and Space
11
Binary Lifting Template
12
Problem - Min Diameter After Merge
13
Min Diameter After Merge - Why Naive Fails
14
Min Diameter After Merge - Defining the DP
15
Min Diameter After Merge - Core Logic
16
Min Diameter After Merge - Implementation
17
Problem - Min Edge Reversals
18
Min Edge Reversals - Why Naive Fails
19
Min Edge Reversals - Defining the DP
20
Min Edge Reversals - Core Logic
21
Min Edge Reversals - Implementation
22
Problem - Collect Apples
23
Small-to-Large Merging
24
Collect Apples - Solution
25
Collect Apples - Why This Works
26
Quiz: Tree Techniques
27
Quiz: Rerooting DP
28
Common Mistakes in Tree Problems
29
Problem - Link Cut Centroids
30
Link Cut Centroids - Solution
31
Problem - Tree Requests
32
Tree Requests - Solution
33
Problem - Kingdom and its Cities
34
Kingdom and its Cities - Solution
35
Problem - Tree Isomorphism II
36
Tree Isomorphism II - Solution
37
Problem - Count on a Tree II
38
Count on a Tree II - Solution
39
Section Recap
Centroid Decomposition
0/30
1
Introduction to Centroid Decomposition
2
What Centroid Decomposition Solves
3
When to Use Centroid Decomposition
4
Centroid Decomposition Template
5
When Centroid Decomposition Helps
6
Problem - IOI Race
7
IOI Race - Why Naive Fails
8
IOI Race - Defining the DP
9
IOI Race - Implementation
10
IOI Race - Time and Space
11
Problem - Distance in Tree
12
Distance in Tree - Why Naive Fails
13
Distance in Tree - Defining the DP
14
Distance in Tree - Core Logic
15
Distance in Tree - Implementation
16
Problem - Xenia and Tree
17
Xenia and Tree - Why Naive Fails
18
Xenia and Tree - Defining the DP
19
Xenia and Tree - Core Logic
20
Xenia and Tree - Implementation
21
Problem - Close Vertices
22
Close Vertices - Solution
23
Quiz: Centroid Properties
24
Quiz: Counting Paths
25
Common Mistakes in Centroid Decomposition
26
Problem - Digit Tree
27
Digit Tree - Solution
28
Problem - Query on a Tree V
29
Query on a Tree V - Solution
30
Section Recap
Graph: Problem Solving - Roadmaps | Repovive