Matrix Traversal Pattern | CodeTutor

Matrix Traversal

Intermediate

35 questions using this pattern

What is Matrix Traversal?

Navigate 2D grids systematically using DFS, BFS, or directional iteration. Matrix traversal combines graph traversal concepts with coordinate-based movement, treating each cell as a node connected to its neighbors.

Think of it like this...

Imagine being dropped into a maze viewed from above. You can move up, down, left, or right, but walls block certain paths. DFS is like exploring one corridor completely before backtracking. BFS is like sending scouts in all directions simultaneously—whoever reaches the exit first found the shortest path.

Another analogy: painting a floor. Flood fill (DFS/BFS) starts at one point and spreads to all connected unpainted tiles.

Core Concept

A 2D grid is essentially a graph where each cell connects to its neighbors (4-directional or 8-directional). The key adaptations from graph traversal:

Nodes are coordinates: Instead of node IDs, track (row, col) pairs
Edges are directions: Neighbors are found by adding direction vectors
Bounds checking: Validate coordinates before accessing the grid
In-place visited marking: Often modify the grid itself instead of using a separate visited set (mark '1' → '0' to indicate visited)

When to use DFS vs BFS:

DFS: Counting regions, checking if path exists, flood fill
BFS: Shortest path, simultaneous spreading from multiple sources

Number of Islands - Matrix Traversal

Matrix Traversal

def numIslands(grid: list[list[str]]) -> int:

    if not grid:

        return 0

    rows, cols = len(grid), len(grid[0])

    count = 0

    def dfs(r: int, c: int):

        if r < 0 or r >= rows or c < 0 or c >= cols:

            return

        if grid[r][c] == '0':

            return

        grid[r][c] = '0'  # Mark visited

        dfs(r + 1, c)  # Down

        dfs(r - 1, c)  # Up

        dfs(r, c + 1)  # Right

        dfs(r, c - 1)  # Left

    for r in range(rows):

        for c in range(cols):

            if grid[r][c] == '1':

                count += 1

                dfs(r, c)

    return count

Variables

No variables yet

Island Grid

Problem

We have a 4x5 grid where '1' represents land and '0' represents water. Our goal is to count distinct islands (connected land regions).

1/23

Visual Walkthrough

Example: Number of Islands

Grid (1 = land, 0 = water):

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

DFS from (0,0): marks all connected 1s as visited
→ Found island 1

Continue scanning, DFS from (2,2):
→ Found island 2

Continue scanning, DFS from (3,3):
→ Found island 3

Answer: 3 islands

Shortest path in grid (BFS):

Grid (0 = passable, 1 = wall):

0 0 0
1 1 0
0 0 0

Start: (0,0)  End: (2,2)

BFS levels:
Level 0: (0,0)
Level 1: (0,1)
Level 2: (0,2)
Level 3: (1,2)
Level 4: (2,2) ← Found! Distance = 4

4-directional vs 8-directional:

4-directional:          8-directional:
    ↑                   ↖ ↑ ↗
  ← ○ →                 ← ○ →
    ↓                   ↙ ↓ ↘

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

from collections import deque

# Direction vectors
DIRS_4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # right, left, down, up
DIRS_8 = [(0, 1), (0, -1), (1, 0), (-1, 0),
          (1, 1), (1, -1), (-1, 1), (-1, -1)]


def is_valid(grid: list[list], row: int, col: int) -> bool:
    """Check if coordinates are within grid bounds."""
    return 0 <= row < len(grid) and 0 <= col < len(grid[0])


def dfs_matrix(grid: list[list[int]], row: int, col: int) -> int:
    """DFS to explore connected region, returns size."""
    if not is_valid(grid, row, col) or grid[row][col] == 0:
        return 0

    grid[row][col] = 0  # Mark as visited (modify in-place)
    size = 1

    for dr, dc in DIRS_4:
        size += dfs_matrix(grid, row + dr, col + dc)

    return size


def count_islands(grid: list[list[str]]) -> int:
    """Count connected regions of '1's."""
    if not grid:
        return 0

    count = 0
    rows, cols = len(grid), len(grid[0])

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs_sink_island(grid, r, c)

    return count


def dfs_sink_island(grid: list[list[str]], row: int, col: int):
    """Sink an island by marking all connected '1's as '0'."""
    if not is_valid(grid, row, col) or grid[row][col] == '0':
        return

    grid[row][col] = '0'  # Sink this cell

    for dr, dc in DIRS_4:
        dfs_sink_island(grid, row + dr, col + dc)


def bfs_shortest_path(grid: list[list[int]],
                      start: tuple, end: tuple) -> int:
    """BFS to find shortest path in grid (0 = passable, 1 = wall)."""
    if grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1:
        return -1

    rows, cols = len(grid), len(grid[0])
    queue = deque([(*start, 0)])  # (row, col, distance)
    visited = {start}

    while queue:
        row, col, dist = queue.popleft()

        if (row, col) == end:
            return dist

        for dr, dc in DIRS_4:
            nr, nc = row + dr, col + dc
            if (is_valid(grid, nr, nc)
                and (nr, nc) not in visited
                and grid[nr][nc] == 0):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return -1  # No path


def multi_source_bfs(grid: list[list[int]]) -> int:
    """BFS from multiple sources (e.g., rotting oranges)."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # Find all sources and count targets
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:  # Rotten orange
                queue.append((r, c, 0))
            elif grid[r][c] == 1:  # Fresh orange
                fresh += 1

    max_time = 0
    while queue:
        row, col, time = queue.popleft()
        max_time = max(max_time, time)

        for dr, dc in DIRS_4:
            nr, nc = row + dr, col + dc
            if is_valid(grid, nr, nc) and grid[nr][nc] == 1:
                grid[nr][nc] = 2  # Mark as rotten
                fresh -= 1
                queue.append((nr, nc, time + 1))

    return max_time if fresh == 0 else -1

Recognition Signals

Look for these keywords and patterns in problem descriptions:

gridmatrix2D arraynumber of islandsshortest path in gridflood fillsurrounded regionsrotting orangesword searchrobot pathmaze

When to Use

Finding connected regions (islands)
Shortest path in a grid
Flood fill / painting
Spreading simulations (rotting oranges, fire spread)
Word search in character grid

Common Mistakes

Modifying grid while using it for bounds checking

If you use grid values for validity checks (like grid[r][c] == '1') and also modify them in-place, you might check a cell you already modified.

Fix:

Modify the cell immediately upon visiting, before exploring neighbors:

grid[row][col] = '0'  # Mark first
for dr, dc in DIRS_4:
    dfs(grid, row + dr, col + dc)  # Then explore

Forgetting to check all starting points

For problems like "number of islands," only starting DFS from (0,0) misses islands not connected to the top-left.

Fix:

Iterate through every cell and start a new traversal from each unvisited cell:

for r in range(rows):
    for c in range(cols):
        if grid[r][c] == '1':
            count += 1
            dfs(grid, r, c)

Pattern Variations

Island counting

Count connected regions of the same value. DFS from each unvisited cell, marking the entire region as visited.

Examples: Number of Islands, Max Area of Island

Shortest path in grid

BFS from start to end, counting levels. Works only if all moves have equal cost (unweighted).

Examples: Shortest Path in Binary Matrix, 01 Matrix

Multi-source BFS

Start BFS from multiple cells simultaneously. Useful for spreading problems where multiple sources expand in parallel.

Examples: Rotting Oranges, Walls and Gates

Word search

DFS with backtracking to find if a word exists in the grid by following adjacent cells. Need to track the current path to avoid reusing cells.

Examples: Word Search, Word Search II

Spiral traversal

Not graph-based, but iterate through matrix in spiral order using boundary tracking (top, bottom, left, right).

Examples: Spiral Matrix, Spiral Matrix II

Learning Path

1Warmup0/7

Start here to build foundational understanding.

Available Captures for RookOptimal

#999Easy

Build Array from PermutationOptimal

#1920Easy

Cells in a Range on an Excel SheetOptimal

#2194Easy

Check if Every Row and Column Contains All NumbersOptimal

#2133Easy

Check if Matrix Is X-MatrixOptimal

#2319Easy

Island PerimeterOptimal

#463Easy

Transpose MatrixOptimal

#867Easy

2Core Practice0/22

Master the pattern with these representative problems.

3Challenge0/6

Test your mastery with complex variations.

Bricks Falling When Hit

#803Hard

Cat and Mouse II

#1728Hard

Check if There Is a Valid Parentheses String PathOptimal

#2267Hard

First Missing PositiveOptimal

#41Hard

Longest Increasing Path in a Matrix

#329Hard

Word Search II

#212Hard

Prerequisites

Learn these patterns first:

BFS (Breadth-First Search)

Level-by-level traversal using a queue, exploring all neighbors at the current depth before moving deeper. This guarantees the shortest path in unweighted graphs and is ideal for problems requiring layer-by-layer processing.

DFS (Depth-First Search)

Explore as deep as possible along each branch before backtracking, using recursion or an explicit stack. DFS is memory-efficient and naturally suited for problems involving paths, connectivity, and exhaustive exploration.

Related Patterns

Explore similar techniques:

Fix:

Always check bounds before accessing:

if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == target:
    # Safe to access

Matrix Traversal

What is Matrix Traversal?

Core Concept

Visual Walkthrough

Code Template

Recognition Signals

When to Use

Common Mistakes

Pattern Variations

Island counting

Shortest path in grid

Multi-source BFS

Word search

Spiral traversal

Learning Path

1Warmup0/7

2Core Practice0/22

3Challenge0/6

Prerequisites

BFS (Breadth-First Search)

DFS (Depth-First Search)

Related Patterns

BFS (Breadth-First Search)

DFS (Depth-First Search)

Backtracking