Grid flood fill (components)

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A map is a grid of cells: 1 for land, 0 for water. Count the islands, where an island is a group of land cells touching along edges (not corners). For a 4 by 5 grid with a block of land in the top left, another block on the right, and a single land cell in the middle, you count 3 by looking at the blobs.

By hand, "count the blobs" is instant for the eye, but try to say what the eye does: it picks an unvisited land cell, then spreads over everything connected to it, then looks for another unvisited land cell. The slow way a computer might do it is: for every pair of land cells, decide whether they are connected by searching a path between them, then group. That is quadratic in the number of land cells and most of it is repeated work.

Build the structure, one piece at a time

Piece one: treat each cell as a node of a graph. Its neighbours are the cells directly above, below, left and right, if they are inside the grid. There is no adjacency list to build; the neighbours are computed from the coordinates.

Piece two: a visited marker per cell. The simplest version writes it into the grid itself, turning a 1 into 0 (or 2) once counted, so no extra memory is needed.

Piece three: flood fill. Standing on a land cell, mark it visited, then do the same for each of its four neighbours that is land and not yet visited. Depth-first with recursion, or breadth-first with a queue; either way the fill stops exactly at the water edge, having marked the whole island.

Piece four: the outer scan. Walk the grid row by row. Each time you meet a land cell that is not yet marked, add one to the island count and flood fill from it.

Why it is correct

The invariant: every marked cell belongs to exactly one counted island, and every island that has had any of its cells marked has been marked completely. The fill guarantees the second half: starting from one cell it marks everything reachable by land steps, which is the whole island by definition. The scan guarantees the first half: it starts a new count only at an unmarked land cell, which cannot belong to an island already filled, since that fill would have marked it.

islands = number of times the scan meets an unmarked land cell

Each island is met exactly once by the scan: at its first cell in row-major order, after which it is fully marked.

Why it is fast

Each cell is looked at by the scan once and marked by a fill at most once, and marking checks four neighbours. Total O(m × n) for an m by n grid. Memory is the recursion stack or queue, up to the size of the largest island in the worst case; iterative BFS avoids deep recursion on a grid that is one huge island.

How to recognise it in an interview

A grid with two kinds of cells and a question about connected groups: "number of islands", "largest island area", "regions fully enclosed", "cells from which water reaches both oceans", "fill a region with a new colour". Say: "I will treat cells as graph nodes, scan the grid, and flood fill from each unvisited cell of the target kind." Number of Islands is this exactly. Max Area of Island makes the fill return the count of cells it marked. Surrounded Regions flips the viewpoint: fill from every border 0 first, so that whatever 0 remains unmarked is enclosed. Pacific Atlantic Water Flow fills uphill from each ocean's edge and intersects the two marked sets.

02The idea in one line

Treat cells as nodes; DFS/BFS from each unvisited land cell and mark the whole island.

Reach for it when: Number of islands, max area, closed islands, surrounded regions, flood fill.

Cost: O(mn) time.

03The walk-through, step by step

The video works one example: Number of Islands on a 4×5 grid. These are its captions in order, so you can follow without the video or check a step you missed.

1. Scan row by row; an unvisited land cell starts a new island
2. Land at (0,0) not yet visited: island #1 starts here
3. Flood fill marks all 4 connected cells as island #1
4. Land at (1,4) not yet visited: island #2 starts here
5. Flood fill marks all 4 connected cells as island #2
6. Land at (2,2) not yet visited: island #3 starts here
7. Flood fill marks all 1 connected cells as island #3
8. Scan done: 3 islands; every land cell was visited exactly once
9. Each cell is marked once: O(m·n)

04Asked at Google

11 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).