Interactive Lab · DSA & Algorithms

Count the islands, then find the shortest way out, flood fill on a grid

A grid is just a graph in disguise: every cell is a node, and it has an edge to its four neighbours. That one idea cracks a whole family of interview questions. Number of Islands is "how many connected blobs of land?", so you scan the grid and, every time you hit land you haven't seen, you flood it and add one to the count. Shortest path in a maze is the same flood, started from S, stopped at T. The only choice you make is the container: a queue (BFS) or a stack (DFS). Paint your own grid and watch which one gets you out the short way.

The setup, the two questions every placement round asks

1 · Number of Islands (LeetCode 200): given a grid of 1 (land) and 0 (water), count the islands. Land connects only up, down, left and right, not diagonally.

2 · Shortest path in a binary maze (LeetCode 1091's 4-way cousin): fewest steps from S to T without walking through a wall. Same flood, one extra rule: stop when you reach T.

▶ The playground, tap or drag to paint, then scrub the flood

problem

strategy

land density 42%

step 0 / 0

🧭 Where this fits

Grid flood fill is everywhere a 2-D map is secretly a graph: the paint-bucket tool in every image editor, counting cells or tumours in a microscope image (connected-component labelling), working out which plots a flood or a wildfire reaches, and robots or game characters finding the fewest-step route across a tile map. In interviews it's the gateway to a dozen problems: Number of Islands, Max Area of Island, Rotting Oranges (multi-source BFS), Surrounded Regions, Walls and Gates. For the same queue-vs-stack idea on a general graph, see the Graph Search lab; once steps have different costs, BFS gives way to Dijkstra.

The code that's actually running, flip BFS/DFS and watch one line change

🔮 Predict, then test

Switch to Shortest path, keep the same maze, and flip between BFS and DFS. Both reach T, and the "steps" number on T is the length of the path each one found. Predict which one is always equal to the true shortest distance, and which one can be much longer. Then go back to Count islands and flip again: the visit order changes completely, but does the island count ever change? Why is that the right answer for islands but the wrong tool for shortest paths?

The takeaway

Your new mental model of grid search

A grid is a graph. Cell = node, four neighbours = edges. Every "connected region" question on a grid is a graph-traversal question, in O(R × C) because each cell is visited once.
Number of Islands = scan + flood. Scan every cell; on unseen land, add one to the count and flood the whole island so you never count it twice. Any traversal works here, BFS and DFS always give the same count, only the visiting order differs.
Mark when you push, not when you pop. Marking a cell as seen the moment it enters the queue/stack stops it being added twice. Forget this and the frontier balloons with duplicates.
BFS = shortest path in an unweighted grid. A queue finishes every cell at distance d before any at d + 1, so the first time it reaches T, it got there by a shortest route. DFS just gets there, often the long way round.
The gotcha: recursion depth. Recursive DFS on a big all-land grid (say 1000 × 1000) can blow Python's recursion limit. An explicit stack or queue, like the code above, never will.

← Graph Search: BFS vs DFS Placement prep →Try: Union-Find