Graph Problems on Matrices: Grids as Implicit Graphs

Many graph problems are disguised as matrix problems. A 2D grid is an implicit graph where each cell is a node and adjacent cells (up, down, left, right) are neighbors connected by edges. You never need to build an explicit adjacency list because the neighbor relationships are defined by the grid coordinates.

This pattern appears constantly in interviews: flood fill, number of islands, shortest path in a grid, surrounded regions, and many more. The key skill is recognizing when a matrix problem is really a graph traversal problem.

The Grid-as-Graph Template

from collections import deque

# Direction arrays for 4-directional movement
DIRS_4 = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Direction arrays for 8-directional movement
DIRS_8 = [(0, 1), (0, -1), (1, 0), (-1, 0),
          (1, 1), (1, -1), (-1, 1), (-1, -1)]


def is_valid(r, c, rows, cols):
    """Check if (r, c) is within grid bounds."""
    return 0 <= r < rows and 0 <= c < cols


def grid_bfs(grid, start_r, start_c):
    """
    BFS template for grid traversal.
    """
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    queue = deque([(start_r, start_c)])
    visited[start_r][start_c] = True

    while queue:
        r, c = queue.popleft()
        # Process cell (r, c)

        for dr, dc in DIRS_4:
            nr, nc = r + dr, c + dc
            if (is_valid(nr, nc, rows, cols)
                    and not visited[nr][nc]
                    and grid[nr][nc] != 0):  # Condition varies
                visited[nr][nc] = True
                queue.append((nr, nc))

Problem 1: Flood Fill (LeetCode 733)

Starting from a pixel, change all connected pixels of the same color to a new color.

def flood_fill(image, sr, sc, new_color):
    """
    LeetCode 733: Flood Fill.
    Change the color of the starting pixel and all connected
    same-colored pixels to new_color.
    """
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]

    if original_color == new_color:
        return image

    def dfs(r, c):
        image[r][c] = new_color
        for dr, dc in DIRS_4:
            nr, nc = r + dr, c + dc
            if (is_valid(nr, nc, rows, cols)
                    and image[nr][nc] == original_color):
                dfs(nr, nc)

    dfs(sr, sc)
    return image

BFS Version

def flood_fill_bfs(image, sr, sc, new_color):
    """Flood fill using BFS."""
    rows, cols = len(image), len(image[0])
    original_color = image[sr][sc]

    if original_color == new_color:
        return image

    queue = deque([(sr, sc)])
    image[sr][sc] = new_color

    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS_4:
            nr, nc = r + dr, c + dc
            if (is_valid(nr, nc, rows, cols)
                    and image[nr][nc] == original_color):
                image[nr][nc] = new_color
                queue.append((nr, nc))

    return image

Example

image = [
    [1, 1, 1],
    [1, 1, 0],
    [1, 0, 1]
]
result = flood_fill(image, 1, 1, 2)
# [[2, 2, 2],
#  [2, 2, 0],
#  [2, 0, 1]]

Problem 2: Number of Islands (LeetCode 200)

Count the number of connected components of ‘1’s in a grid.

DFS Approach

def num_islands_dfs(grid):
    """
    LeetCode 200: Number of Islands.
    Count connected components of '1' cells.
    """
    if not grid:
        return 0

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

    def dfs(r, c):
        if (not is_valid(r, c, rows, cols)
                or grid[r][c] != '1'):
            return
        grid[r][c] = '0'  # Mark as visited by sinking
        for dr, dc in DIRS_4:
            dfs(r + dr, c + dc)

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

    return count

BFS Approach

def num_islands_bfs(grid):
    """Number of islands using BFS."""
    if not grid:
        return 0

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

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

                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in DIRS_4:
                        nr, nc = cr + dr, cc + dc
                        if (is_valid(nr, nc, rows, cols)
                                and grid[nr][nc] == '1'):
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count

Union-Find Approach

Union-Find avoids modifying the grid and supports online updates (cells added one at a time).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 0

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1

    def add(self):
        self.count += 1


def num_islands_uf(grid):
    """Number of islands using Union-Find."""
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                uf.add()
                idx = r * cols + c
                # Union with right and down neighbors
                if c + 1 < cols and grid[r][c + 1] == '1':
                    uf.union(idx, idx + 1)
                if r + 1 < rows and grid[r + 1][c] == '1':
                    uf.union(idx, idx + cols)

    return uf.count

Example

grid = [
    ['1', '1', '0', '0', '1'],
    ['1', '0', '0', '0', '1'],
    ['0', '0', '0', '1', '1'],
    ['0', '0', '0', '0', '0']
]
print(num_islands_dfs([row[:] for row in grid]))  # 3

Problem 3: Shortest Path in Binary Matrix (LeetCode 1091)

Find the shortest path from top-left to bottom-right in a binary grid, allowing 8-directional movement.

def shortest_path_binary_matrix(grid):
    """
    LeetCode 1091: Shortest Path in Binary Matrix.
    0 = open, 1 = blocked. 8-directional movement.
    Returns length of shortest path, or -1.
    """
    n = len(grid)
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    queue = deque([(0, 0, 1)])  # row, col, path_length
    grid[0][0] = 1  # Mark visited

    while queue:
        r, c, dist = queue.popleft()

        if r == n - 1 and c == n - 1:
            return dist

        for dr, dc in DIRS_8:
            nr, nc = r + dr, c + dc
            if is_valid(nr, nc, n, n) and grid[nr][nc] == 0:
                grid[nr][nc] = 1
                queue.append((nr, nc, dist + 1))

    return -1

Example

grid = [
    [0, 0, 0],
    [1, 1, 0],
    [1, 1, 0]
]
print(shortest_path_binary_matrix(grid))  # 4
# Path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)

Problem 4: Surrounded Regions (LeetCode 130)

Flip all ‘O’ regions that are completely surrounded by ‘X’. The trick: instead of finding surrounded regions (hard), find un-surrounded regions (easy) by starting from the border.

def solve(board):
    """
    LeetCode 130: Surrounded Regions.
    Flip surrounded 'O' to 'X'.
    """
    if not board:
        return

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

    def dfs(r, c):
        """Mark border-connected 'O' cells as safe."""
        if (not is_valid(r, c, rows, cols)
                or board[r][c] != 'O'):
            return
        board[r][c] = 'S'  # Safe (connected to border)
        for dr, dc in DIRS_4:
            dfs(r + dr, c + dc)

    # Step 1: Mark all border-connected 'O' as safe
    for r in range(rows):
        dfs(r, 0)
        dfs(r, cols - 1)
    for c in range(cols):
        dfs(0, c)
        dfs(rows - 1, c)

    # Step 2: Flip remaining 'O' to 'X', restore 'S' 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 5: Max Area of Island (LeetCode 695)

Find the largest connected component of 1’s.

def max_area_of_island(grid):
    """
    LeetCode 695: Max Area of Island.
    Returns the area of the largest island.
    """
    rows, cols = len(grid), len(grid[0])
    max_area = 0

    def dfs(r, c):
        if (not is_valid(r, c, rows, cols)
                or grid[r][c] != 1):
            return 0
        grid[r][c] = 0  # Mark visited
        area = 1
        for dr, dc in DIRS_4:
            area += dfs(r + dr, c + dc)
        return area

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                max_area = max(max_area, dfs(r, c))

    return max_area

Problem 6: Pacific Atlantic Water Flow (LeetCode 417)

Find cells that can reach both the Pacific (top/left border) and Atlantic (bottom/right border) oceans.

def pacific_atlantic(heights):
    """
    LeetCode 417: Pacific Atlantic Water Flow.
    Water flows from higher to lower cells.
    Find cells that reach both oceans.
    """
    if not heights:
        return []

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

    def dfs(r, c, reachable, prev_height):
        if ((r, c) in reachable
                or not is_valid(r, c, rows, cols)
                or heights[r][c] < prev_height):
            return
        reachable.add((r, c))
        for dr, dc in DIRS_4:
            dfs(r + dr, c + dc, reachable, heights[r][c])

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

    # Flow from Atlantic border (bottom and right)
    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)

Problem 7: Rotting Oranges (with BFS Distance)

This is a multi-source BFS problem covered in the multi-source BFS article, but here is a compact version using grid-as-graph thinking.

def oranges_rotting(grid):
    """Minimum time for all oranges to rot."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    time = -1
    while queue:
        time += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in DIRS_4:
                nr, nc = r + dr, c + dc
                if (is_valid(nr, nc, rows, cols)
                        and grid[nr][nc] == 1):
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return time if fresh == 0 else -1

Avoiding Common Pitfalls

Pitfall 1: Not Marking Visited Before Enqueueing

# WRONG: Mark when dequeuing (leads to duplicates)
while queue:
    r, c = queue.popleft()
    if visited[r][c]:
        continue
    visited[r][c] = True  # Too late!
    for dr, dc in DIRS_4:
        nr, nc = r + dr, c + dc
        queue.append((nr, nc))  # Duplicates!

# CORRECT: Mark when enqueueing
queue.append((r, c))
visited[r][c] = True  # Mark immediately
while queue:
    r, c = queue.popleft()
    for dr, dc in DIRS_4:
        nr, nc = r + dr, c + dc
        if not visited[nr][nc]:
            visited[nr][nc] = True  # Mark before push
            queue.append((nr, nc))

Pitfall 2: Recursion Depth for Large Grids

DFS on a 1000x1000 grid can exceed Python’s default recursion limit (1000). Use BFS or increase the limit.

import sys
sys.setrecursionlimit(1000000)  # For competitive programming

# Or convert DFS to iterative:
def iterative_dfs(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    stack = [(start_r, start_c)]
    grid[start_r][start_c] = 0

    while stack:
        r, c = stack.pop()
        for dr, dc in DIRS_4:
            nr, nc = r + dr, c + dc
            if (is_valid(nr, nc, rows, cols)
                    and grid[nr][nc] == 1):
                grid[nr][nc] = 0
                stack.append((nr, nc))

Pitfall 3: Modifying Grid When You Need It Later

If you modify the grid to mark visited cells but need the original later, either use a separate visited array or make a copy.

# Option A: Separate visited array
visited = [[False] * cols for _ in range(rows)]

# Option B: Copy the grid
import copy
grid_copy = copy.deepcopy(grid)

Complexity Summary

All grid traversal problems have the same fundamental complexity:

Metric	Value
Time	O(rows * cols)
Space	O(rows * cols) for visited/queue
Nodes	rows * cols
Edges	Up to 4 * rows * cols

Practice Problems

1. Flood Fill (LeetCode 733) - Basic DFS/BFS on grid
2. Number of Islands (LeetCode 200) - Connected components
3. Max Area of Island (LeetCode 695) - Largest component
4. Shortest Path in Binary Matrix (LeetCode 1091) - BFS shortest path
5. Surrounded Regions (LeetCode 130) - Border DFS
6. Pacific Atlantic Water Flow (LeetCode 417) - Dual BFS/DFS
7. Number of Enclaves (LeetCode 1020) - Border-connected analysis
8. Count Sub Islands (LeetCode 1905) - Island comparison

Key Takeaways

A 2D grid is an implicit graph. Each cell is a node, adjacent cells are neighbors, and no adjacency list is needed. The direction array pattern (DIRS_4 or DIRS_8) lets you iterate over neighbors cleanly. DFS works for connected components and reachability. BFS works for shortest paths. Union-Find works for dynamic connectivity. Mark cells as visited before pushing to avoid duplicates. For large grids in Python, prefer iterative approaches or increase the recursion limit.