DFS on a 2D Grid: Islands and Flood Fill

Preamble

A 2D grid of '1' and '0' is a graph: each cell is a node; 4-directional (or 8-directional) neighbors are edges. Number of islands is the canonical interview pattern—DFS or BFS counts connected components of land. The graph abstraction is the lesson; the syntax is incidental.

DFS pattern

From each unvisited land cell, flood the component: mark visited (flip to '0', use a visited set, or a second bool matrix if immutability matters). Increment the island count once per flood start.

Neighbor iteration is four lines of delta arrays—(r+1,c), (r-1,c), etc.—with bounds checks.

Recursion depth

Python recursion limits hurt on huge grids. An explicit stack (list or deque as stack) preserves DFS order without blowing the interpreter stack. BFS with a queue also works; for unweighted components both visit each cell once—O(rows × cols) time.

Conclusion

Same complexity story as graph DFS on an adjacency list—the grid is just an implicit graph. BFS for Layered State Spaces in Java implements BFS in Java for word-ladder-style layered search. Algorithms Retrospective: DFS, BFS, Dijkstra, and Backtracking ties these patterns together in a retrospective.