Grid Traversal Islands and Flood Fill

A grid is a graph you never have to build. Each cell is a node; its edges are the neighbours you can step to. That single reframing turns a large family of matrix problems into ordinary DFS or BFS — no adjacency list required, because (r+1, c)(r+1, c), (r-1, c)(r-1, c), (r, c+1)(r, c+1), (r, c-1)(r, c-1) is the adjacency function.

What remains is bookkeeping: staying in bounds, not revisiting cells, and knowing which of the two traversals the question wants.

What you’ll learn

The four-direction template, and why sinksink (mutate in place) usually beats a visitedvisited set.
Counting connected components — the outer loop that makes island counting work.
DFS vs BFS on grids: identical for counting, different for shortest paths and for stack depth.
The boundary-inversion trick — the idea behind LC 130, 1020 and 417, and the most transferable insight here.
Three real LeetCode problems solved in the browser: 200, 695, 733.

The cue

The template

grid_dfs_template.py

def count_regions(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
 
    def sink(r, c):
        # bounds check and "is it land" check, both in the base case
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return
        grid[r][c] = 0                       # mark visited by mutating
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)
 
    regions = 0
    for r in range(rows):                    # the outer scan finds each region
        for c in range(cols):
            if grid[r][c] == 1:
                regions += 1                 # a new region begins here
                sink(r, c)                   # then erase all of it
    return regions

grid_dfs_template.py

def count_regions(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
 
    def sink(r, c):
        # bounds check and "is it land" check, both in the base case
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != 1:
            return
        grid[r][c] = 0                       # mark visited by mutating
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)
 
    regions = 0
    for r in range(rows):                    # the outer scan finds each region
        for c in range(cols):
            if grid[r][c] == 1:
                regions += 1                 # a new region begins here
                sink(r, c)                   # then erase all of it
    return regions

Two structural pieces to internalise:

The base case does both checks. Bounds first, then “is this a cell I care about”. Testing bounds at the call site instead means four copies of the same condition.
The outer double loop is the component counter. sinksink erases one entire region, so the number of times the outer loop starts a sink is the number of regions. This is exactly connected-component counting from Graph Traversal.

DFS or BFS?

	DFS	BFS
Count / measure regions	✅ equally good	✅ equally good
Shortest path in a grid	❌ wrong	✅ correct
Space	$O(rc)$ worst-case recursion	$O(\min(r, c))$ -ish frontier
Risk	Python `RecursionErrorRecursionError` on a large solid grid	none

For counting they are interchangeable — pick either. For shortest path only BFS works, because BFS visits in non-decreasing distance order.

A 200×200 grid that is entirely land is 40,000 cells in one region, and a recursive sinksink can nest that deep — far past Python’s default 1000-frame limit. On LeetCode’s larger grid problems this is a real RecursionErrorRecursionError.

Two fixes: sys.setrecursionlimit(...)sys.setrecursionlimit(...), or write it iteratively with an explicit stack:

python

stack = [(r, c)]
while stack:
    cr, cc = stack.pop()
    if 0 <= cr < rows and 0 <= cc < cols and grid[cr][cc] == 1:
        grid[cr][cc] = 0
        stack.extend([(cr+1, cc), (cr-1, cc), (cr, cc+1), (cr, cc-1)])

python

stack = [(r, c)]
while stack:
    cr, cc = stack.pop()
    if 0 <= cr < rows and 0 <= cc < cols and grid[cr][cc] == 1:
        grid[cr][cc] = 0
        stack.extend([(cr+1, cc), (cr-1, cc), (cr, cc+1), (cr, cc-1)])

Note the check happens on pop, not before pushing — that keeps the loop body to one guard, at the cost of pushing some cells that get discarded. Both orderings are fine as long as you are consistent.

Direction vectors

For anything beyond four directions, a vector list beats four hard-coded calls:

direction_vectors.py

DIRS_4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS_8 = DIRS_4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))
 
for dr, dc in DIRS_4:
    nr, nc = r + dr, c + dc
    ...

direction_vectors.py

DIRS_4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
DIRS_8 = DIRS_4 + ((1, 1), (1, -1), (-1, 1), (-1, -1))
 
for dr, dc in DIRS_4:
    nr, nc = r + dr, c + dc
    ...

Eight-direction connectivity (LC 1254 and many “count blobs” variants) is then a one-token change rather than four more recursive calls.

The boundary-inversion trick

This is the idea worth carrying away from this page. Several problems ask about regions that do not touch the border — captured regions, enclaves. Searching for “regions with no border cell” directly is awkward: you would have to explore a region fully, then decide.

Invert it. Flood inward from the border to mark everything that is connected to the edge. Whatever remains unmarked is, by definition, enclosed.

surrounded_regions_130.py

def solve(board):
    """LC 130: flip every 'O' region NOT touching the border to 'X'."""
    if not board or not board[0]:
        return board
    rows, cols = len(board), len(board[0])
 
    def mark_safe(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != "O":
            return
        board[r][c] = "S"                     # temporarily: reachable from edge
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            mark_safe(r + dr, c + dc)
 
    for r in range(rows):                     # start ONLY from the border
        mark_safe(r, 0)
        mark_safe(r, cols - 1)
    for c in range(cols):
        mark_safe(0, c)
        mark_safe(rows - 1, c)
 
    for r in range(rows):                     # then a single rewrite pass
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"
    return board

surrounded_regions_130.py

def solve(board):
    """LC 130: flip every 'O' region NOT touching the border to 'X'."""
    if not board or not board[0]:
        return board
    rows, cols = len(board), len(board[0])
 
    def mark_safe(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != "O":
            return
        board[r][c] = "S"                     # temporarily: reachable from edge
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            mark_safe(r + dr, c + dc)
 
    for r in range(rows):                     # start ONLY from the border
        mark_safe(r, 0)
        mark_safe(r, cols - 1)
    for c in range(cols):
        mark_safe(0, c)
        mark_safe(rows - 1, c)
 
    for r in range(rows):                     # then a single rewrite pass
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "S" else "X"
    return board

Once you see this, LC 130 (capture regions), LC 1020 (count enclaves) and LC 417 (Pacific-Atlantic water flow) are all the same three-step recipe: flood from the border, then read off what was or was not reached. LC 417 runs it twice — once from each ocean — and intersects the results.

	Time	Space
Any single grid traversal	$O(r \cdot c)$	$O(r \cdot c)$ worst case for the stack/queue

The variant map

Variant	What changes	Canonical problem
Count regions	Count outer-loop starts	200 Number of Islands
Measure regions	`sinksink` returns a size; take the max	695 Max Area of Island
Recolour one region	Start from a given cell only	733 Flood Fill
Border inversion	Flood from the border, then invert	130 · 1020
Two-source reachability	Flood from each source, intersect	417 Pacific Atlantic
Shortest path	BFS, not DFS	1091 · Multi-source BFS
8-direction connectivity	`DIRS_8DIRS_8` instead of `DIRS_4DIRS_4`	1254 and blob-counting variants
Count perimeter, not area	Add 4 per land cell, subtract 2 per shared edge	463 Island Perimeter

Practice — real LeetCode problems

LC 200 — Number of Islands · Medium

Problem. Given an m x nm x n binary grid of '1''1' (land) and '0''0' (water), return the number of islands. An island is land connected horizontally or vertically, surrounded by water.

Constraints. 1 <= m, n <= 3001 <= m, n <= 300, cells are the characters '0''0' or '1''1'.

Examples. A grid with one large connected landmass gives 11; a grid with three separate landmasses gives 33; all water gives 00.

Editorial — approach, complexity, follow-ups

This is connected-component counting on an implicit graph. The outer loop finds an unvisited land cell — necessarily a new island, since any previously seen island has been erased — and the sink removes the whole component.

Time $O(m \cdot n)$ : each cell is examined a constant number of times. Space $O(m \cdot n)$ worst case for the stack.

Two practical notes:

String cells. LeetCode gives "1""1" and "0""0" as characters here (unlike LC 695, which uses integers). Comparing against 11 silently finds nothing and returns 00. It is an irritating inconsistency and a real source of wasted submissions.
Iterative over recursive. At 300 x 300300 x 300 a solid grid is 90,000 cells in one component. Recursive DFS raises RecursionErrorRecursionError; the explicit stack does not.

Follow-ups you should expect:

“Don’t mutate the input.” Use a visitedvisited set of (r, c)(r, c) at $O(mn)$ space.
“8-directional islands?” Swap in DIRS_8DIRS_8.
“The grid is a stream / too large for memory.” Process row by row with union-find, merging components between adjacent rows — this is the real-world answer and a common senior follow-up.
“Islands II — land added one cell at a time (LC 305)?” Union-find with a running component count, since each addition can merge up to four components.
“Count distinct island shapes (LC 694)?” Normalise each island’s cell offsets relative to its starting cell and hash the resulting tuple.

LC 695 — Max Area of Island · Medium

Problem. Given an m x nm x n binary grid of 00 and 11 integers, return the area (number of cells) of the largest island. If there is no island, return 00.

Constraints. 1 <= m, n <= 501 <= m, n <= 50, cells are the integers 00 or 11.

Examples. The standard 8×13 example gives 66 · [[0,0],[0,0]][[0,0],[0,0]] gives 00 · [[1]][[1]] gives 11

Editorial — approach, complexity, follow-ups

Identical structure to LC 200, except the recursion returns a count instead of nothing. Because areaarea zeroes each cell as it enters, no cell contributes twice, and the returned sum is exactly the island’s size.

Time $O(m \cdot n)$ . Space $O(m \cdot n)$ recursion worst case (fine here at 50 x 5050 x 50, unlike LC 200’s 300 x 300300 x 300).

Two details:

Mark before recursing. If you set grid[r][c] = 0grid[r][c] = 0 after the four recursive calls, a neighbour immediately recurses back into this cell and you double-count — or recurse forever. The ordering is load-bearing.
default=0default=0 on maxmax. With no land at all, the generator yields only zeros so it happens to work here — but on a grid with no cells at all maxmax of an empty sequence raises ValueErrorValueError. default=0default=0 is the safe habit.

Recursion is acceptable at these constraints, which is why this solution reads more cleanly than LC 200’s iterative one. Choosing per-problem based on the stated bounds — rather than always doing one or the other — is the judgement being tested.

Follow-ups you should expect: “Count the perimeter instead (LC 463)?” — add 4 per land cell and subtract 2 for each shared edge; no traversal needed at all. “Return the largest island’s cells?” — collect coordinates instead of counting. “Largest island after flipping one 00 to 11 (LC 827)?” — label each island with an id and its size, then for every water cell sum the sizes of its distinct neighbouring island ids plus one.

LC 733 — Flood Fill · Easy

Problem. Given an imageimage grid, a starting pixel (sr, sc)(sr, sc) and a colorcolor, recolour the starting pixel and every pixel connected to it (4-directionally) that shares the starting pixel’s original colour.

Constraints. 1 <= m, n <= 501 <= m, n <= 50, 0 <= pixel values, color < 2^160 <= pixel values, color < 2^16.

Examples. [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2[[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2 gives [[2,2,2],[2,2,0],[2,0,1]][[2,2,2],[2,2,0],[2,0,1]] · filling with the colour it already has leaves the image unchanged

Editorial — approach, complexity, follow-ups

A single traversal from one starting cell. Recolouring doubles as the visited mark: once a cell is colorcolor it no longer matches startstart, so the guard stops re-entry.

Time $O(m \cdot n)$ . Space $O(m \cdot n)$ recursion worst case.

Note also that the visited-marking and the goal-writing are the same operation here, which is unusual and pleasant. In LC 200 you overwrite with a sentinel you do not care about; here the overwrite is the answer.

Follow-ups you should expect: “Iteratively?” — an explicit stack, same guard. “8-directional?” — DIRS_8DIRS_8. “What if colorcolor should replace only cells matching a given colour rather than the start’s?” — pass it in; the guard becomes a comparison against that value. “Fill with a gradient / bounded distance?” — switch to BFS so you know each cell’s distance from the source.

LeetCode problem set

#	Problem	Difficulty	The twist
733	Flood Fill	Easy	The `start == colorstart == color` guard, or infinite recursion
463	Island Perimeter	Easy	No traversal needed: 4 per land cell, minus 2 per shared edge
200	Number of Islands	Medium	Component counting; cells are strings here
695	Max Area of Island	Medium	The sink returns a size; mark before recursing
130	Surrounded Regions	Medium	Boundary inversion — flood from the border, then rewrite
1020	Number of Enclaves	Medium	Boundary inversion, then count what survives
417	Pacific Atlantic Water Flow	Medium	Flood uphill from each ocean, then intersect

Interview follow-ups

They ask	What they’re checking	The answer
“DFS or BFS?”	Deliberate choice	Interchangeable for counting; BFS is required for shortest path
“Do you mutate the input?”	Care about side effects	Sinking is $O(1)$ space but destructive; a `visitedvisited` set is $O(mn)$ and clean. State the trade
“What about a huge solid grid?”	Practical Python	Recursive DFS can exceed the 1000-frame limit; use an explicit stack
“Regions not touching the border?”	The transferable trick	Flood from the border and invert — do not test regions one at a time
“The grid doesn’t fit in memory”	Real-world thinking	Stream row by row with union-find, merging components across adjacent rows
“Land is added incrementally”	Choosing the right structure	Union-find with a running component count (LC 305)
“8 directions instead of 4?”	Generalisation	A `DIRSDIRS` vector list makes it a one-line change

Edge-case checklist

Empty grid — [][] or [[]][[]]; guard before reading grid[0]grid[0].
1×1 grid — both [[1]][[1]] (one island, area 1) and [[0]][[0]] (zero).
All land — one island covering everything; the recursion-depth case.
All water — 00 islands, 00 area; max(..., default=0)max(..., default=0).
Start colour equals target colour (LC 733) — must return immediately.
Islands touching the border — fine for 200/695, the whole point for 130/1020.
Diagonally adjacent land — not connected under 4-directional rules; a frequent misreading.
String vs integer cells — LC 200 uses "1""1", LC 695 uses 11. Check before comparing.
Single row or single column — exercises bounds checks in one dimension.

Recap

A grid is an implicit graph: the four neighbour offsets are the adjacency function, so no graph needs building.
The base case does bounds plus validity in one place; the outer double loop counts components.
Sink the grid for $O(1)$ space, or keep a visitedvisited set to avoid mutating the input — and say which you chose.
DFS and BFS are interchangeable for counting; only BFS gives shortest paths.
Mark before recursing, or cells get counted twice and recursion can loop.
Boundary inversion — flood inward from the border and invert — is the key to 130, 1020 and 417. Do not test regions one at a time.
Watch Python’s recursion limit on large solid grids; an explicit stack is the safe default.

Next: Multi-source BFS — what to do when the search starts from many cells at once, and why that is still a single $O(mn)$ pass.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Grid Traversal Islands and Flood Fill

What you’ll learn

The cue

The template

DFS or BFS?

Direction vectors

The boundary-inversion trick

The variant map

Practice — real LeetCode problems

LC 200 — Number of Islands · Medium

LC 695 — Max Area of Island · Medium

LC 733 — Flood Fill · Easy

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?