Depth First Search (DFS)
Recursive and iterative DFS, discovery/finish times, DFS tree, and back edges.
41 lessons
137 min
Lessons
1. Intro
The concept of exploring
2m
2. The Visited Array
The Chalk Mark
2m
3. The DFS Logic Flow
Step-by-Step
3m
4. The Code Template
Memorize this
5m
5. How to Call It
Starting the engine
2m
6. Visualizing the Trace
Dry Run
5m
7. Quiz: DFS Traversal Order
Knowledge check
2m1 problems
8. Time Complexity of DFS
How fast is it?
3m
9. Space Complexity of DFS
Memory usage
3m
10. Quiz: DFS Complexity
Knowledge check
2m1 problems
11. LeetCode 133 Clone Graph - Problem Statement
(LeetCode 133)
4m1 problems
12. LeetCode 133 Clone Graph - Strategy
How DFS works
2m
13. LeetCode 133 Clone Graph - Why Depth First
Why do we call it that?
2m
14. LeetCode 133 Clone Graph - Handling Cycles
The Infinite Loop
3m
15. LeetCode 133 Clone Graph - Core Idea
(Hash map tracks copies)
4m
16. LeetCode 133 Clone Graph - Algorithm
(Recursive copy pattern)
4m
17. LeetCode 133 Clone Graph - Recursion
The nature of DFS
3m
18. LeetCode 133 Clone Graph - Implementation
(Python solution)
4m1 problems
19. LeetCode 133 Clone Graph - Lessons
Graph change strategy
4m
20. Quiz: Cycle Handling in DFS
Knowledge check
2m1 problems
21. LeetCode 841 Keys and Rooms - Problem Statement
LeetCode 841
2m1 problems
22. LeetCode 841 Keys and Rooms - Mapping
Translating to Graphs
3m
23. LeetCode 841 Keys and Rooms - Solution
Using DFS
5m
24. LeetCode 841 Keys and Rooms - Implementation
Coding it
5m1 problems
25. Connected Components
Broken Graphs
3m
26. Counting Components - The Idea
How to find them all
3m
27. Counting Components - Algorithm
The Loop
3m
28. Quiz: Connected Components
Knowledge check
2m1 problems
29. LeetCode 547 Number of Provinces - Problem Statement
LeetCode 547
3m1 problems
30. LeetCode 547 Number of Provinces - Input
Adjacency Matrix Trap
4m
31. LeetCode 547 Number of Provinces - Implementation
The Code
8m1 problems
32. DFS on Trees
A simpler graph
3m
33. Avoiding Cycles in Trees
The Parent Trick
3m
34. Carrying State in DFS
The Backpack
3m
35. Quiz: DFS on Trees
Knowledge check
2m1 problems
36. Codeforces 580C Kefa and Park - Problem Statement
Codeforces 580C
3m1 problems
37. Codeforces 580C Kefa and Park - State
What to carry?
4m
38. Codeforces 580C Kefa and Park - Logic
Updating the State
5m
39. Codeforces 580C Kefa and Park - Implementation
Coding the logic
8m1 problems
40. Quiz: DFS State Tracking
Knowledge check
2m1 problems
41. Section Recap
What we learned
2m
Practice Problems
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.