Graphs
A grid is a graph
Cells are nodes, adjacency is edges, and the visited mark is permanent. That last word is the whole lesson.
Key idea
The reframe
A grid is a graph in disguise. Each cell is a node and each pair of side-by-side cells is an edge. Nothing about the traversal cares that the nodes are arranged in a rectangle.
That means the tree traversals from Unit 8 apply directly, with one addition. A tree has no way back to where you came from; a grid does, so a traversal that does not remember where it has been will bounce between two adjacent cells forever.
Why it works
Marked once, never unmarked
In Unit 10 the grid mark was undone on the way out, because every distinct path mattered. Here it is not, because arriving at a cell once is enough to know it belongs to this region.
That single difference is the whole cost story, and it is worth seeing as a number rather than as an assertion. Below, the same two-by-two board is walked twice: once marking permanently, once undoing the mark the way a path search would.
Key idea
The outer loop counts, the inner one consumes
The structure is two nested pieces with different jobs. The outer double loop looks for any unvisited cell that could start a region. The flood consumes an entire region so that none of its cells can start another.
So the outer loop runs once per cell and the answer increments once per region. Getting this split clear in your head is most of the work; the flood itself is mechanical.
Gotcha
Mark on push or mark on pop, but know which
Marking when a cell is popped means a cell can be pushed several times before it is processed, so the loop needs a second check at the top to skip one it has already handled. Without that recheck the same cell gets counted repeatedly.
Marking at the moment of pushing guarantees each cell enters the stack once and needs no recheck at all. Both are correct, and marking on push keeps the stack smaller, so it is the better habit. What is not correct is doing neither, or doing one and then writing the loop as though you had done the other.
Tip
Recursion or an explicit stack
Written recursively the flood is shorter and reads better. On a large grid it can exceed Python's recursion limit, since the depth can reach the number of cells in one region.
For interview-sized inputs recursion is fine and clearer. Mention that an explicit stack avoids the depth limit if the constraints are large, which is exactly the kind of remark that costs one sentence and signals real awareness.
Key idea
Returning something from the flood
Counting regions needs nothing back from the flood. Measuring them needs a size, and the change is small: have the flood return how many cells it consumed and take the largest.
Same traversal, different reading, which is the pattern from the level-order lesson in Unit 8. Both problems below are this traversal with a different line at the end.
Cost
Cost
Every cell is visited at most once and each visit examines four neighbors, so O(rows times cols) time. The visited set is the same size, and the stack can hold a whole region in the worst case, so O(rows times cols) space.
The four is a constant and drops out. Saying linear in the number of cells is the right level of precision.
Flood fill drills
Three readings of one traversal, none of which is a plain count. region_of returns the sorted cells of the region containing a given cell. bounding_box returns the smallest rectangle enclosing that region, as [top, left, bottom, right]. regions_touching_border counts how many separate regions of X touch any edge of the board. Cells connect side to side only, not diagonally.
Tests
board = [
["X", "X", ".", "."],
["X", ".", ".", "X"],
[".", ".", "X", "X"],
]
print(region_of(board, 0, 0))
print(bounding_box(board, 0, 0), bounding_box(board, 2, 3))
print(region_of(board, 0, 2), bounding_box(board, 0, 2))
print(regions_touching_border(board), regions_touching_border([[".", "."]]))Output
Run the tests when you are ready.
Number Of Islands
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Max Area Of Island
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.