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, 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 sink (mutate in place) usually beats a visited 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

You are looking at grid traversal when…

• The input is a 2D grid and you need regions: count them, measure them, recolour them — 200, 695, 733, 463.
• “Connected” cells, by 4 or 8 directions — 200, 1254.
• Cells reachable from the border (or not) — 130, 1020, 417.
• Shortest path through a grid — BFS specifically; see Multi-source BFS when there are many sources.

The anti-cue: if you are rearranging the grid — rotating, spiralling, transposing — that is Matrix and Grid Manipulation, not traversal. Searching a grid is this page; reshaping one is not.

Visual intuition

A grid is a graph in disguise — nodes are cells, edges are adjacency. Counting islands is therefore connected components, an algorithm from earlier in this phase wearing a 2-D costume:

gridCount one, then flood it so it is never counted twiceLC 200 · O(rows x cols)

1111111

stack

empty

islands0

1def num_islands(grid):2    rows, cols = len(grid), len(grid[0])3    count = 04    for r in range(rows):5        for c in range(cols):6            if grid[r][c] == '1':7                count += 1          # a NEW island8                flood(grid, r, c)   # sink all of it9    return count10 11def flood(grid, r, c):12    stack = [(r, c)]13    while stack:14        r, c = stack.pop()15        if not in_bounds or grid[r][c] != '1': continue16        grid[r][c] = '0'            # mark visited BY SINKING it17        for dr, dc in DIRS:18            stack.append((r + dr, c + dc))

setupScan every cell. The moment an unclaimed piece of land is found, it must belong to an island nobody has counted yet — so increment the counter and then flood the whole island so it is never counted twice.

Play‹›1/12⟲

The flood is what keeps the outer double loop linear rather than quadratic: every cell is claimed exactly once across the whole run, no matter how many times the scan passes over it.

gridBFS labels every reachable cell with its shortest distanceO(rows x cols)

0◉

queue

0,0

start0,0goal4,4visited1

1def shortest_path(grid, start, end):2    q = deque([(start, 0)])3    seen = {start}4    while q:5        (r, c), d = q.popleft()6        if (r, c) == end:7            return d               # first arrival IS shortest8        for dr, dc in DIRS:9            nr, nc = r + dr, c + dc10            if in_bounds and grid[nr][nc] != '#' and (nr, nc) not in seen:11                seen.add((nr, nc))12                q.append(((nr, nc), d + 1))13    return -1

setupEach cell will be labelled with its distance from the start. BFS fills outward in rings, so the first time it touches a cell that distance is already the shortest — no revisiting, no relaxation.

Play‹›1/19⟲

Cells are marked visited on ENQUEUE, not on dequeue. Marking on dequeue lets the same cell enter the queue several times, which is the standard way this solution degrades from linear to quadratic.

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

Two structural pieces to internalise:

1. 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.
2. The outer double loop is the component counter. sink 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.

Sink the grid, or keep a visited set?

Mutating the grid to mark visited cells is $O(1)$ extra space and one line shorter. A visited set costs $O(rc)$ space but leaves the input untouched.

In an interview, say which you are doing and why. “I’ll sink the grid for $O(1)$ space — but that mutates the caller’s input, so if that matters I’d use a visited set instead” is a much better answer than silently destroying the argument. Some interviewers care a great deal about not mutating inputs.

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 RecursionError 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.

Recursive DFS can blow the stack on a big grid

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

Two fixes: 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)])

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
    ...

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

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

Complexity

Let the grid be $r \times c$, so $n = rc$ cells.

Quantity	Cost	Why
Time	$O(rc)$	each cell is sunk at most once, and each sink looks at 4 neighbours
Space, sinking the grid	$O(rc)$ recursion, $O(1)$ extra data	the call stack is the cost, and it is invisible in the source
Space, BFS + queue	$O(\min(r, c))$ typical, $O(rc)$ worst	the queue holds one frontier
Space, visited set instead of sinking	$O(rc)$	buys you an unmutated input

The outer double loop does not multiply the cost. It visits $rc$ cells and starts a sink only on cells that are still land, and each sink permanently removes the cells it touches — so across the whole run every cell is entered once. Counting the outer loop and the sinks separately, and then adding rather than multiplying them, is the argument to give out loud.

The recursive version’s space is the trap

”$O(1)$ space because I mutate the grid” is wrong, and interviewers ask about it. The DFS recursion is $O(rc)$ deep in the worst case — a $200 \times 200$ grid of all 1s is one snake-shaped region 40,000 cells long, and CPython raises RecursionError past about 1000 frames. The honest answers are ”$O(rc)$ stack, or an explicit stack / BFS queue to make it heap-allocated instead”.

Dry run

grid = [[1,1,0],[1,0,1],[0,0,1]], the template exactly as written. The outer scan goes row by row; sink recurses down, up, right, left in that order.

#	outer loop at	action	grid after
1	(0,0) is land	regions = 1, start sink	—
2		sink (0,0) → mark 0, recurse down	[[0,1,0],[1,0,1],[0,0,1]]
3		sink (1,0) → mark 0; its 4 neighbours are (2,0)=0, (0,0)=already sunk, (1,1)=0, out of bounds — all return	[[0,1,0],[0,0,1],[0,0,1]]
4		back at (0,0): up is out of bounds; right → sink (0,1) → mark 0; its neighbours are (1,1)=0, oob, (0,2)=0, (0,0) sunk	[[0,0,0],[0,0,1],[0,0,1]]
5	(0,1), (0,2), (1,0), (1,1)	all now 0 — skipped, no sink started	—
6	(1,2) is land	regions = 2, start sink	—
7		sink (1,2) → mark 0, down → sink (2,2) → mark 0	[[0,0,0],[0,0,0],[0,0,0]]
8	(2,0), (2,1), (2,2)	all 0 — nothing starts	—

Answer 2.

What the trace shows that the code does not:

• regions counts sink starts, not cells. The outer loop passes over five already-sunk land cells (step 5) without incrementing anything, because sinking erased them. That is the entire component-counting mechanism, and it is why no separate visited bookkeeping is needed.
• Every sink call that does real work is guarded by the same two-part base case. Step 3 makes four recursive calls and all four return immediately — one for bounds, three for “not land”. Roughly 4 calls per cell do nothing, which is why the constant factor is 5× the cell count and still $O(rc)$.
• The recursion is 3 deep here and $rc$ deep in the worst case. Follow step 2 → 3: sink(0,0) is still on the stack while sink(1,0) runs. On a spiral-shaped island of 40,000 cells that stack is 40,000 frames tall — the concrete reason the ”$O(1)$ space” claim fails.

The variant map

Variant	What changes	Canonical problem
Count regions	Count outer-loop starts	200 Number of Islands
Measure regions	sink 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_8 instead of DIRS_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 n binary grid of '1' (land) and '0' (water), return the number of islands. An island is land connected horizontally or vertically, surrounded by water.

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

Examples. A grid with one large connected landmass gives 1; a grid with three separate landmasses gives 3; all water gives 0.

pch.exerciseTag pch.exerciseTitle

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" and "0" as characters here (unlike LC 695, which uses integers). Comparing against 1 silently finds nothing and returns 0. It is an irritating inconsistency and a real source of wasted submissions.
• Iterative over recursive. At 300 x 300 a solid grid is 90,000 cells in one component. Recursive DFS raises RecursionError; the explicit stack does not.

Follow-ups you should expect:

• “Don’t mutate the input.” Use a visited set of (r, c) at $O(mn)$ space.
• “8-directional islands?” Swap in DIRS_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 n binary grid of 0 and 1 integers, return the area (number of cells) of the largest island. If there is no island, return 0.

Constraints. 1 <= m, n <= 50, cells are the integers 0 or 1.

Examples. The standard 8×13 example gives 6 · [[0,0],[0,0]] gives 0 · [[1]] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Identical structure to LC 200, except the recursion returns a count instead of nothing. Because area 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 50, unlike LC 200’s 300 x 300).

Two details:

• Mark before recursing. If you set grid[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=0 on max. 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 max of an empty sequence raises ValueError. default=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 0 to 1 (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 image grid, a starting pixel (sr, sc) and a color, recolour the starting pixel and every pixel connected to it (4-directionally) that shares the starting pixel’s original colour.

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

Examples. [[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]] · filling with the colour it already has leaves the image unchanged

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

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

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

The one line that makes this problem non-trivial

if start == color: return image is essential. Without it, recolouring is a no-op: the cell still matches start, so a neighbour recurses straight back into it, and the two bounce until the stack overflows.

Cases 2 and 3 both exercise it — filling colour 0 onto a 0 pixel and colour 1 onto a 1 pixel. Both must return the image unchanged. This is why an “Easy” problem still fails a lot of submissions, and it is a good reminder that “already in the goal state” deserves an explicit check.

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_8. “What if color 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

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 417 inverts the flow, not just the boundary

Pacific Atlantic Water Flow asks which cells can drain to both oceans. Simulating downhill flow from every cell is $O((mn)^2)$.

Invert it twice over. Start from each ocean’s border cells and walk uphill (only onto neighbours with height >= current), marking everything reachable. A cell reachable in the Pacific pass can drain to the Pacific; same for the Atlantic. The answer is the intersection of the two sets.

Two floods, $O(mn)$, and the trick is the same “start from the boundary and reverse the relation” move as LC 130 — applied to the direction of flow rather than to membership.

10 problems

2 easy5 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○463Island PerimetereasyNo traversal needed: 4 per land cell, minus 2 per shared edge
• ○733Flood FilleasyThe `start == color` guard, or infinite recursion
• ○200Number of IslandsmediumComponent counting; cells are **strings** hereNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbytedance
• ○130Surrounded RegionsmediumBoundary inversion -- flood from the border, then rewriteNeetCode 150LeetCode Top Interview 150
• ○417Pacific Atlantic Water FlowmediumFlood **uphill** from each ocean, then intersectNeetCode 150Blind 75
• ○695Max Area of IslandmediumThe sink returns a size; mark before recursingNeetCode 150
• ○1020Number of EnclavesmediumBoundary inversion, then count what survives
• ○329Longest Increasing Path in a MatrixhardNeetCode 150
• ○1368Minimum Cost to Make at Least One Valid Path in a Gridhard
• ○2290Minimum Obstacle Removal to Reach Cornerhard

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 visited 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 DIRS vector list makes it a one-line change

Edge-case checklist

• Empty grid — [] or [[]]; guard before reading grid[0].
• 1×1 grid — both [[1]] (one island, area 1) and [[0]] (zero).
• All land — one island covering everything; the recursion-depth case.
• All water — 0 islands, 0 area; 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", LC 695 uses 1. Check before comparing.
• Single row or single column — exercises bounds checks in one dimension.

Self-check

pch.quizTag Grid traversal — self-check

1. The outer double loop visits every cell and can start a sink at each one. Why is the total still O(rc) rather than O((rc)²)?

   A Because most grids are sparse B Because a sink permanently erases the cells it touches, so across the whole run each cell is entered once — the outer scan and the sinks add, they do not multiply C Because the outer loop breaks after the first island D Because DFS is O(1) per call
   pch.quizShowAnswer

   B — Because a sink permanently erases the cells it touches, so across the whole run each cell is entered once — the outer scan and the sinks add, they do not multiply — In the dry run the outer loop passes over five already-sunk cells without doing anything. Being able to say 'these costs add' is the difference between guessing the complexity and deriving it.

2. Is the recursive sinking solution O(1) space?

   A Yes — it mutates the grid instead of allocating B No — the DFS recursion is O(rc) deep in the worst case, and on a large solid grid CPython raises RecursionError past about 1000 frames C Yes, because Python optimises tail calls D Only if the grid is square
   pch.quizShowAnswer

   B — No — the DFS recursion is O(rc) deep in the worst case, and on a large solid grid CPython raises RecursionError past about 1000 frames — The extra *data* is O(1); the call stack is not, and it is invisible in the source. A 200×200 all-land grid is one region 40,000 cells long. The safe answers are an explicit stack or BFS.

3. Where do the bounds check and the 'is this land' check belong?

   A At each call site, before recursing B Both in the base case of the recursive function, so there is exactly one copy of each C Bounds at the call site, land check in the base case D In the outer loop
   pch.quizShowAnswer

   B — Both in the base case of the recursive function, so there is exactly one copy of each — Guarding at the call site means four copies of the same condition per recursion — four chances to typo one of them. One base case doing both is the shape to memorise.

4. You mark a cell visited *after* recursing into its neighbours instead of before. What breaks?

   A Nothing B Neighbours recurse back into the unmarked cell, so cells are counted twice and the recursion can revisit forever C Only the area count is wrong, not the island count D It becomes BFS
   pch.quizShowAnswer

   B — Neighbours recurse back into the unmarked cell, so cells are counted twice and the recursion can revisit forever — Mark-then-recurse is the invariant. It is the grid version of 'mark on enqueue, not on dequeue' from the BFS pages.

5. LC 130 asks you to capture every region NOT touching the border. Why not test each region separately?

   A It is too slow B Because it inverts the work: flood inward from the border cells to mark the surviving regions, then flip everything unmarked — one pass instead of a border test per region C Because regions can overlap D Because DFS cannot detect border contact
   pch.quizShowAnswer

   B — Because it inverts the work: flood inward from the border cells to mark the surviving regions, then flip everything unmarked — one pass instead of a border test per region — Boundary inversion is the trick behind LC 130, 1020 and 417. Deciding 'does this region touch the border' region-by-region is both more code and easy to get wrong; starting from the border makes the answer structural.

Recall card

• Cue — a 2-D grid where adjacent same-valued cells form regions: count them, measure them, or recolour one.
• Idea — the grid is the graph; the four offsets (1,0) (-1,0) (0,1) (0,-1) are the adjacency function. Nothing gets built.
• Template — base case checks bounds and validity; mark before recursing; the outer double loop counts sink starts, which is the component count.
• Visited — sink the grid (mutates the caller’s input) or a visited set ($O(rc)$ space). Say which and why.
• Cost — $O(rc)$ time; the recursion is $O(rc)$ deep worst case, so use an explicit stack or BFS on large grids. ”$O(1)$ space” is a wrong answer.
• Boundary inversion — for “regions not touching the edge” (LC 130, 1020, 417), flood inward from the border and invert.
• Read the cell type — "1" in LC 200, 1 in LC 695; diagonals are not adjacent under 4-directional rules.

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 visited 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.