Algorithms / Grid Graph Traversal
Least You Need to Know: Grid Traversal, Flood Fill, and Boundary Checks
Many interview grid problems are just implicit graph traversal: each cell is a node, legal moves define edges, and BFS or DFS visits connected components or shortest paths. The main implementation risk is careful neighbor and boundary handling.
Least you need to know
- A grid becomes a graph when each cell connects to its legal neighbors.
- Flood fill is component traversal over cells that meet a condition.
- Boundary checks must happen before reading or enqueueing a neighbor cell.
- Marking visited prevents repeated exploration and infinite revisits.
- Counting islands is counting connected components in an implicit grid graph.
Key notation
- (r, c) — row and column state
- 4-neighbors — up, down, left, right
- component — maximal connected region under the movement rule
Worked example
- To count islands, scan the grid for an unvisited land cell.
- Each time you find one, start DFS or BFS and mark its whole connected land region.
- That one traversal claims exactly one island.
- Continue scanning until all land cells are assigned to some traversal.
Common mistakes
- Students often forget to check bounds before reading neighbors.
- Students often mutate or revisit cells in inconsistent order and double-count regions.
- Students often choose DFS for shortest path in an unweighted maze when BFS is the better fit.
How to recognize it
- The input is a matrix with legal moves to neighboring cells.
- You need to count regions, spread through a region, or find a shortest route on equal-cost moves.
- The graph is implicit; neighbors are generated from coordinates rather than listed explicitly.
Next recommended lesson
Continue through this topic with Least You Need to Know: K-Way Merge, Top-K, and Heap Frontier Ideas.
Least You Need to Know: K-Way Merge, Top-K, and Heap Frontier IdeasRelated lessons
Keep going with nearby lessons in the same topic.