Matrix DFS

Many graph problems are presented as 2D grids (matrices). DFS on a matrix explores connected regions by recursively visiting adjacent cells. This pattern solves island counting, flood fill, and many other grid problems.

Grid as a Graph

A 2D grid can be viewed as a graph where:

• Each cell is a vertex
• Adjacent cells (up, down, left, right) are connected by edges

Grid:          As Graph:
1 1 0          (0,0) - (0,1)
1 0 0            |
0 0 1          (1,0)
                          (2,2)

Each '1' is a node, '0' is blocked

Basic DFS on Grid

use std::collections::HashSet;

fn dfs(grid: &[Vec<i32>], row: isize, col: isize, visited: &mut HashSet<(isize, isize)>) {
    // Check bounds
    if row < 0 || row >= grid.len() as isize || col < 0 || col >= grid[0].len() as isize {
        return;
    }

    // Check if already visited or blocked
    if visited.contains(&(row, col)) || grid[row as usize][col as usize] == 0 {
        return;
    }

    visited.insert((row, col));

    // Explore all 4 directions
    dfs(grid, row + 1, col, visited);  // Down
    dfs(grid, row - 1, col, visited);  // Up
    dfs(grid, row, col + 1, visited);  // Right
    dfs(grid, row, col - 1, visited);  // Left
}

Direction Arrays

Use direction arrays to simplify exploration:

use std::collections::HashSet;

// 4 directions: up, down, left, right
const DIRECTIONS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

// 8 directions: including diagonals
const DIRECTIONS_8: [(isize, isize); 8] = [
    (-1, 0), (1, 0), (0, -1), (0, 1),
    (-1, -1), (-1, 1), (1, -1), (1, 1)
];

fn dfs(grid: &[Vec<i32>], row: isize, col: isize, visited: &mut HashSet<(isize, isize)>) {
    if row < 0 || row >= grid.len() as isize || col < 0 || col >= grid[0].len() as isize {
        return;
    }
    if visited.contains(&(row, col)) || grid[row as usize][col as usize] == 0 {
        return;
    }

    visited.insert((row, col));

    for &(dr, dc) in &DIRECTIONS {
        dfs(grid, row + dr, col + dc, visited);
    }
}

Problem: Number of Islands

Count distinct islands (connected regions of 1s):

Grid:
1 1 0 0 0
1 0 0 1 1
0 0 0 1 0
0 0 0 0 0

Islands: 2 (top-left group, middle-right group)

use std::collections::HashSet;

fn count_islands(grid: &[Vec<char>]) -> i32 {
    if grid.is_empty() {
        return 0;
    }

    let rows = grid.len();
    let cols = grid[0].len();
    let mut visited = HashSet::new();
    let mut count = 0;

    fn dfs(grid: &[Vec<char>], r: isize, c: isize, rows: usize, cols: usize,
           visited: &mut HashSet<(isize, isize)>) {
        if r < 0 || r >= rows as isize || c < 0 || c >= cols as isize {
            return;
        }
        if visited.contains(&(r, c)) || grid[r as usize][c as usize] == '0' {
            return;
        }

        visited.insert((r, c));

        for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
            dfs(grid, r + dr, c + dc, rows, cols, visited);
        }
    }

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == '1' && !visited.contains(&(r as isize, c as isize)) {
                dfs(grid, r as isize, c as isize, rows, cols, &mut visited);
                count += 1;
            }
        }
    }

    count
}

Problem: Max Area of Island

Find the largest island:

fn max_area_island(grid: &mut [Vec<i32>]) -> i32 {
    if grid.is_empty() {
        return 0;
    }

    let rows = grid.len();
    let cols = grid[0].len();
    let mut max_area = 0;

    fn dfs(grid: &mut [Vec<i32>], r: isize, c: isize, rows: usize, cols: usize) -> i32 {
        if r < 0 || r >= rows as isize || c < 0 || c >= cols as isize {
            return 0;
        }
        if grid[r as usize][c as usize] == 0 {
            return 0;
        }

        grid[r as usize][c as usize] = 0;  // Mark as visited
        let mut area = 1;

        for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
            area += dfs(grid, r + dr, c + dc, rows, cols);
        }

        area
    }

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == 1 {
                max_area = max_area.max(dfs(grid, r as isize, c as isize, rows, cols));
            }
        }
    }

    max_area
}

Problem: Flood Fill

Change all connected cells of the same color:

def flood_fill(image, sr, sc, new_color):
    if not image:
        return image

    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]

    if original_color == new_color:
        return image

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original_color:
            return

        image[r][c] = new_color

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

    dfs(sr, sc)
    return image

Problem: Surrounded Regions

Capture all 'O's not connected to the border:

Before:              After:
X X X X              X X X X
X O O X     →        X X X X
X X O X              X X X X
X O X X              X O X X

'O' at (3,1) touches border, stays 'O'

def solve(board):
    if not board:
        return

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

    # Mark border-connected 'O's as safe
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if board[r][c] != 'O':
            return

        board[r][c] = 'S'  # Safe

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

    # Start DFS from border cells
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

    # Convert remaining 'O' to 'X', 'S' back to 'O'
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'
            elif board[r][c] == 'S':
                board[r][c] = 'O'

Problem: Pacific Atlantic Water Flow

Find cells that can flow to both oceans:

def pacific_atlantic(heights):
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()

    def dfs(r, c, reachable, prev_height):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if (r, c) in reachable or heights[r][c] < prev_height:
            return

        reachable.add((r, c))

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

    # Pacific: top row and left column
    for c in range(cols):
        dfs(0, c, pacific, heights[0][c])
    for r in range(rows):
        dfs(r, 0, pacific, heights[r][0])

    # Atlantic: bottom row and right column
    for c in range(cols):
        dfs(rows - 1, c, atlantic, heights[rows - 1][c])
    for r in range(rows):
        dfs(r, cols - 1, atlantic, heights[r][cols - 1])

    return list(pacific & atlantic)

Iterative DFS

Use an explicit stack to avoid recursion limits:

def count_islands_iterative(grid):
    if not grid:
        return 0

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

    def dfs(start_r, start_c):
        stack = [(start_r, start_c)]

        while stack:
            r, c = stack.pop()

            if r < 0 or r >= rows or c < 0 or c >= cols:
                continue
            if (r, c) in visited or grid[r][c] == '0':
                continue

            visited.add((r, c))

            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                stack.append((r + dr, c + dc))

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

    return count

Time and Space Complexity

• Time: O(rows × cols) — each cell visited once
• Space: O(rows × cols) — for visited set or recursion stack

Key Takeaways

1. Treat 2D grids as graphs with adjacent cells as neighbors
2. Use direction arrays for cleaner code
3. Mark visited cells to avoid infinite loops
4. DFS explores one region completely before moving to the next
5. Many grid problems (islands, flood fill, regions) use this pattern
6. Consider iterative DFS for large grids to avoid stack overflow

Matrix DFS is a fundamental pattern that appears constantly in coding interviews and competitive programming. Master this pattern, and you'll recognize its applications in many problems.