Breadth First Search (BFS)
Level-order traversal, unweighted shortest path, multi-source BFS, and BFS applications.
40 lessons
122 min
Lessons
1. Intro
Why we need something else
2m
2. The Ripple Effect
BFS Intuition
2m
3. The Data Structure
Stack vs Queue
3m
4. The BFS Strategy
Level by Level
3m
5. The BFS Algorithm Step 1
Setup
2m
6. The BFS Algorithm Step 2
Initialization
3m
7. The BFS Algorithm Step 3
The Loop
4m
8. Why does this find Shortest Path?
The Logic
3m
9. Quiz: BFS Shortest Path Guarantee
Knowledge check
2m1 problems
10. Tracking Distances
The Distance Array
3m
11. Implicit Graphs
Graphs in disguise
3m
12. Complexity of BFS
Time and Space
3m
13. Quiz: BFS Complexity
Knowledge check
2m1 problems
14. DFS vs BFS Summary
When to use what?
3m
15. BFS Variants Summary
When to use which BFS
5m
16. LeetCode 1091 Shortest Path in Binary Matrix - Problem Statement
LeetCode 1091
2m1 problems
17. LeetCode 1091 Shortest Path in Binary Matrix - Grid BFS
Adapting the Graph
3m
18. LeetCode 1091 Shortest Path in Binary Matrix - Implementation Details
Storing Coordinates
3m
19. LeetCode 1091 Shortest Path in Binary Matrix - Direction Arrays
A Pro Tip
4m
20. CSES 1667 Message Route - Problem Statement
CSES Problem Set
2m1 problems
21. CSES 1667 Message Route - Path Reconstruction Idea
Breadcrumbs
3m
22. CSES 1667 Message Route - Path Reconstruction Algorithm
Backtracking
4m
23. CSES 1667 Message Route - Implementation
Coding the Path
5m1 problems
24. Quiz: BFS Path Reconstruction
Knowledge check
2m1 problems
25. LeetCode 127 Word Ladder - Problem Statement
Seeing the Graph
4m1 problems
26. LeetCode 127 Word Ladder - Finding Neighbors
The hard part
5m
27. LeetCode 127 Word Ladder - Implementation
LeetCode 127
2m1 problems
28. LeetCode 994 Rotting Oranges - Problem Statement
LeetCode 994
2m1 problems
29. LeetCode 994 Rotting Oranges - Core Idea
Start from all sources
3m
30. LeetCode 994 Rotting Oranges - Algorithm
Level-by-level spread
4m
31. LeetCode 994 Rotting Oranges - Implementation
The code
5m1 problems
32. LeetCode 994 Rotting Oranges - Lessons
Multi-source pattern
3m
33. Quiz: Multi-Source BFS
Knowledge check
2m1 problems
34. LeetCode 542 01 Matrix - Problem Statement
LeetCode 542
2m1 problems
35. LeetCode 542 01 Matrix - Core Idea
Reverse the perspective
3m
36. LeetCode 542 01 Matrix - Algorithm
BFS from all zeros
4m
37. LeetCode 542 01 Matrix - Implementation
The code
5m1 problems
38. LeetCode 542 01 Matrix - Lessons
Distance to nearest source
3m
39. Quiz: BFS vs DFS for Shortest Path
Knowledge check
2m1 problems
40. Section Recap
What we learned
2m
Practice Problems
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.