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.
The 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
Tiny 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 this kind of problem
- 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.