Graph Traversal
Use DFS or BFS with visited tracking to explore one connected component at a time.
0 of 3 problems solved
Graph Traversal
Use DFS or BFS with visited tracking to explore one connected component at a time.
- •Do I need to count connected land regions?
- •Should I mark visited cells so I do not recount them?
- •Will DFS or BFS clear one whole island at a time?
Number of Islands is really a counting problem plus a flood-fill. Every time you find unvisited land, you discovered a brand-new island. Then you immediately explore all connected land from there and mark it visited so you never count that island again. DFS or BFS both work because the real goal is to clear one connected component at a time.
Count the island once, then erase its entire footprint from future consideration.
- 1Scan the grid cell by cell.
- 2When you see unvisited land, increment the island count.
- 3Run DFS or BFS to visit every connected land cell.
- 4Mark visited cells so they are never counted again.
If you do not mark visited land immediately, the same island can be counted multiple times from different entry points.
Flood Fill
DFS from the starting cell. Change each visited cell to the new color, then recurse into its four neighbors if they still carry the original color.
Longest Increasing Path in a Matrix
DFS with memoization. For each cell compute the longest path stepping only to strictly larger neighbors. Cache results per cell.