Island (Matrix Traversal)

DFS or BFS on a 2D grid. Four directions. One flood-fill. The outer loop handles disconnected islands — the inner DFS sinks each one entirely.

Frequency:★★★★★

·~25 min·Beginner–Intermediate·7 problems

Prev Union Find

The Core Shock

Nested loops count cells. Wrong. Flood-fill DFS counts connected components. Correct.

Nested loops only

Counts cells

A 5-cell island gets counted 5 times — no connectivity awareness

Outer loop + DFS

Counts islands

DFS sinks entire island on first encounter — outer loop skips it

The insight: when the outer loop finds a '1', immediately DFS to mark ALL connected '1's as visited. The outer loop then never sees them again. Each cell is visited exactly once — O(m×n). Every island/connected-region problem on a matrix uses this exact outer-loop + flood-fill skeleton.

4-Directional Movement

Memorize these — they appear in every grid DFS/BFS problem.

Inline (4 calls)

dfs(r+1, c)  # down
dfs(r-1, c)  # up
dfs(r, c+1)  # right
dfs(r, c-1)  # left

Loop (cleaner, extensible)

dirs = [(1,0),(-1,0),(0,1),(0,-1)]
for dr, dc in dirs:
    dfs(r+dr, c+dc)

Bounds check first, always: if r<0 or r>=rows or c<0 or c>=cols: return
Then check cell value. Never check value before bounds — that's an IndexError.
8-directional (include diagonals): add (1,1),(1,-1),(-1,1),(-1,-1) to dirs.

The 3-Step Framework

Same 3 steps for every island / matrix traversal problem.

Outer loop: scan every cell

Iterate every (r,c) in the grid. When you find a trigger cell (e.g. '1' for land, 0 for island, old_color for flood fill), increment your counter and immediately flood-fill from that cell.

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == '1':   # unvisited land
            islands += 1
            dfs(r, c)           # flood fill

The counter increment happens in the outer loop, not inside DFS. DFS only marks cells — it doesn't count.

DFS: bounds → value → mark → recurse

Check bounds first. Then check if the cell is the target value. Then mark it (mutate in-place or add to visited set). Then recurse in all 4 directions. This order prevents IndexError and infinite loops.

def dfs(r, c):
    if r<0 or r>=rows or c<0 or c>=cols: return  # bounds
    if grid[r][c] != '1': return                  # value
    grid[r][c] = '0'                              # mark
    dfs(r+1,c); dfs(r-1,c)                        # recurse
    dfs(r,c+1); dfs(r,c-1)

In-place mutation (grid[r][c]='0') is the cleanest approach. Use a visited set only if you can't mutate the input.

For constrained problems: pre-process borders

Closed islands, surrounded regions: first DFS from ALL border cells to eliminate border-touching components. Then do the normal outer-loop + DFS count on what remains. Two-pass approach — always O(m×n).

# Pass 1: eliminate border-connected
for r in range(rows):
    for c in range(cols):
        if on_border(r,c,rows,cols):
            if grid[r][c] == target:
                dfs(r, c, sink_value)

# Pass 2: count remaining
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == target:
            count += 1; dfs(r, c, visited_value)

The two-pass technique works for any 'not touching border' constraint. First pass uses the same DFS template but marks with a different value.

Pattern Recognition

Matrix + connectivity = Island pattern. Always.

Use Island Pattern When

"Number of islands", "connected components" in grid

"Largest island", "maximum area" in matrix

"Flood fill", "change connected region color"

"Closed islands", "enclosed regions"

"Surrounded regions" (convert O→X border rule)

"Perimeter of island" (count border edges)

"Number of distinct shapes" in binary matrix

Any 2D grid where cells connect to neighbors

Common Pitfalls

Bounds check after value check → IndexError

Not marking cell before recursing → infinite loop

Flood fill: old_color == new_color → infinite loop without guard

Closed islands: counting border-touching islands by mistake

Using '0'/'1' strings vs 0/1 ints — check the input type

Biggest island: forgetting to track max (only returns last island size)

Perimeter: counting ALL edges instead of only boundary edges

Forgetting to restore grid if input must not be mutated

On this page