LeetCode Grid Problems: The 11 That Cover Every Pattern

You know BFS. You know DFS. You've coded them from scratch so many times you can write the template half-asleep. Then a grid problem shows up and you spend ten minutes debugging an off-by-one in your bounds check, the multi-source optimization never occurs to you, and your visited set is three times larger than it needs to be.

The algorithms haven't changed. The framing has.

These 11 LeetCode grid problems cover every grid pattern that shows up in interviews. Work through them in order and the shape of each new problem gets easier to read.

Grid Problems Are Just Graph Problems in a Trench Coat

Each cell is a node with up to four neighbors. BFS and DFS work identically to how they work on any other graph. The extra friction comes from translating graph concepts into row-column arithmetic with bounds checks.

That's basically the only friction. Two grid-specific ideas change how you approach these problems. First, you can usually mark visited in-place by overwriting the cell value itself, which means no separate set. Second, some problems want you to seed BFS from multiple starting cells simultaneously rather than one. Get these two ideas down and most grid problems feel like familiar territory.

Slightly hostile familiar territory. But familiar.

The Template All DFS Grid Problems Use

1. Flood Fill (Easy, LC 733)

Start here regardless of your experience level. Fill a region of connected same-colored cells with a new color. It's essentially MS Paint, but you have to implement it from scratch in an interview.

The in-place trick: change the current cell's color before recursing. When DFS revisits a cell, the color has already changed, so it exits early. No separate visited set.

def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    def dfs(r, c):
        if not (0 <= r < len(image) and 0 <= c < len(image[0])):
            return
        if image[r][c] != old:
            return
        image[r][c] = color
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r + dr, c + dc)
    dfs(sr, sc)
    return image

This four-directional DFS with bounds check and early exit is the frame every other DFS grid problem borrows. Flood Fill earns its place first because it shows the template without any distractions. Every problem after this is Flood Fill with one additional idea bolted on.

2. Number of Islands (Medium, LC 200)

Count connected '1' regions in a binary grid. This is the most frequently cited grid problem in interview prep, and with good reason: it introduces the one thing about grid DFS that actually trips people up.

That thing is the outer loop. You need to iterate over every cell and launch DFS whenever you find an unvisited '1'. Without the outer loop, you count only the island containing your starting cell and miss everything else. Candidates solve the DFS part perfectly, skip the outer loop, and then spend a minute wondering why a grid full of islands returns 1. You are not bad at graphs. You just forgot the loop.

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                count += 1
                dfs(grid, r, c)  # marks entire island as visited
    return count

Mark visited by flipping '1' to '0' in-place. Each DFS call consumes one complete island. The outer-loop-plus-DFS structure is the connected components pattern and it shows up in dozens of variants: number of provinces, count enclosed regions, number of distinct islands. Learn it here.

3. Max Area of Island (Medium, LC 695)

Same connected-component structure as Number of Islands. The DFS returns the size of the region instead of void.

Return 1 + sum_of_neighbor_sizes at each call, track the global maximum outside.

def dfs(grid, r, c):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] != 1:
        return 0
    grid[r][c] = 0
    return 1 + sum(dfs(grid, r+dr, c+dc) for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])

Once DFS returns a value instead of void, you can compute any property of a connected region. Perimeter, sum, shape hash. The mechanics don't change, just what you do with the result.

Seed All Sources Before the Loop

4. 01 Matrix (Medium, LC 542)

Distance from every cell to its nearest 0.

The wrong approach: BFS from each '1' cell individually. That's O(n²m²) on an n×m grid. Your interviewer has a 45-minute slot and human feelings. Do not do this.

Reverse the question. Instead of asking how far a '1' is from a '0', ask how far each '0' reaches. Seed all '0' cells into the queue before the loop starts, then let BFS expand outward simultaneously.

Cells reached earlier get smaller distances. Everything else starts at infinity and gets updated when BFS waves wash over it.

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[r][c] + 1 < dist[nr][nc]:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist

The diagram below shows how distances radiate from all three source cells simultaneously in one BFS pass.

Multi-source BFS: three source cells expand outward in parallel, filling the grid in one pass

All three zeros expand in lockstep. The wave that reaches a cell first wins.

The seed-all-sources-first pattern is worth recognizing by name. Once you see it in 01 Matrix, the next problem makes sense immediately.

5. Rotting Oranges (Medium, LC 994)

All rotten oranges spread to fresh neighbors each minute. Find the number of minutes until everything rots, or -1 if it can't happen.

Same multi-source BFS. The wrinkle: you need the time. BFS processes nodes level by level, and each level corresponds to one minute. Count levels as you process.

Track your initial fresh orange count. Decrement it as oranges rot during BFS. If fresh > 0 when the queue empties, return -1. The level count is your answer.

Common mistake: counting outer while-loop iterations instead of true BFS levels. Use the for _ in range(len(queue)) snapshot pattern to process one full level at a time, then increment time. Confusing these two gives you the right answer on simple cases and wrong answers on everything else, which is the most annoying category of bug to debug.

Two Cells Decide Every Grid DP Problem

6. Unique Paths (Medium, LC 62)

Count paths from top-left to bottom-right moving only right or down.

Each cell is reachable from exactly one direction: above it or to its left. dp[i][j] = dp[i-1][j] + dp[i][j-1], with the entire top row and left column initialized to 1.

Space optimization: you only ever need the current row and the row above, so a single 1D array works. This rolling-array reduction from O(m×n) to O(n) applies to most grid DP problems and interviewers notice when you mention it without being prompted.

7. Minimum Path Sum (Medium, LC 64)

Minimum-cost path from top-left to bottom-right. Same recurrence shape, min instead of sum.

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Modifying the input grid in-place works if the interviewer allows it. Not elegant. Very fast to write.

These two problems establish the grid DP template. Any problem with directional movement on a rectangle and optimal substructure probably starts here. See the dynamic programming framework if the recurrence derivation isn't automatic yet.

Word Search Looks Like DFS. It Isn't.

8. Word Search (Medium, LC 79)

Find a target word in a grid by following adjacent cells. No cell can be reused in a single path.

In pure DFS you mark cells visited and never restore them. Here you must undo the marking when you backtrack. Replace the current cell with a sentinel '#' before recursing, then restore the original character when the recursion returns. This is backtracking, not DFS.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[idx]:
            return False
        temp = board[r][c]
        board[r][c] = '#'
        found = any(dfs(r+dr, c+dc, idx+1) for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)])
        board[r][c] = temp
        return found
    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Mixing up DFS and backtracking is the most common Word Search bug. In pure DFS you mark and never restore. In backtracking you always restore. The bug is usually one missing line: board[r][c] = temp. That line looks trivial. It is not trivial. It is the entire algorithm.

Flip the Question, Not the Algorithm

9. Pacific Atlantic Water Flow (Medium, LC 417)

Find all cells whose water can flow to both the Pacific (top and left borders) and the Atlantic (bottom and right borders). Water flows from higher or equal elevation to lower.

The forward approach: compute reachability from every cell. Expensive, messy, and produces wrong answers the first time you implement it.

The reverse: which cells can be reached from each ocean, moving uphill? BFS or DFS inward from each ocean's border cells, only visiting neighbors with elevation greater than or equal to the current cell.

Run two passes, one per ocean, building two visited sets. Return their intersection. The total work is O(nm). You do less work, not more, by reversing direction. This feels suspicious the first time. It works.

This reverse-traversal insight generalizes. Any time a problem asks "can X reach Y?" and X is a large set of cells, consider starting from Y and asking "what can reach me?".

Two Hard Problems. One Non-Obvious Move Each.

10. Longest Increasing Path in a Matrix (Hard, LC 329)

Find the longest strictly increasing path in the grid, starting from any cell, moving in four directions.

The instinct is DFS with a visited set to prevent cycles. Reasonable instinct. Wrong instinct.

Strictly increasing means no path ever revisits a cell because you can never go up and then come back to the same value. The grid is implicitly a DAG. DFS is safe without any visited set. The only risk is recomputing the same result from the same starting cell, which memoization handles.

from functools import lru_cache

def longest_increasing_path(matrix):
    rows, cols = len(matrix), len(matrix[0])
    @lru_cache(maxsize=None)
    def dfs(r, c):
        return 1 + max(
            (dfs(r+dr, c+dc)
             for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]
             if 0 <= r+dr < rows and 0 <= c+dc < cols
             and matrix[r+dr][c+dc] > matrix[r][c]),
            default=0
        )
    return max(dfs(r, c) for r in range(rows) for c in range(cols))

Recognizing the implicit DAG is what separates candidates who finish this in 15 minutes from candidates who stay stuck on the visited set question for 30. Strictly increasing, strictly decreasing, or any monotonic constraint on edge traversal tends to eliminate cycles. When cycles are impossible, you don't need to track them.

11. Shortest Path with Obstacles Elimination (Hard, LC 1293)

Shortest path from top-left to bottom-right in a binary grid (1 = obstacle), where you can eliminate at most k obstacles.

Standard BFS tracks (row, col). That breaks here. Two cells at the same position but with different remaining eliminations are completely different states. A cell you reached after burning three eliminations is worth more than one you reached after burning zero. Standard BFS can't tell these apart and will cheerfully give you wrong answers.

Your BFS node must be (row, col, eliminations_remaining). Your visited set must track all three dimensions.

from collections import deque

def shortest_path(grid, k):
    rows, cols = len(grid), len(grid[0])
    queue = deque([(0, 0, k, 0)])      # r, c, remaining_elim, steps
    visited = {(0, 0, k)}
    while queue:
        r, c, rem, steps = queue.popleft()
        if r == rows - 1 and c == cols - 1:
            return steps
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            new_rem = rem - grid[nr][nc]
            if new_rem >= 0 and (nr, nc, new_rem) not in visited:
                visited.add((nr, nc, new_rem))
                queue.append((nr, nc, new_rem, steps + 1))
    return -1

The rule: when (row, col) alone doesn't determine whether revisiting a cell is worth trying, add the extra context as a state dimension. This problem is the cleanest example. Once you see it here, you recognize the pattern in problems like "shortest path with at most k turns" or "minimum cost path with at most m teleports."

Patterns Worth Naming

DFS for connected regions. BFS for shortest distances. This one rule resolves most algorithm questions on grids.
Multi-source BFS: seed all sources into the queue before the loop starts. One BFS, not n separate BFS calls.
Grid DP: dp[i][j] depends on dp[i-1][j] and dp[i][j-1]. Rolling arrays cut the space for free.
Backtracking on grids: mark in-place with a sentinel, restore on return. Never skip the restore step.
Reverse traversal: when "can X reach Y?" is expensive, flip to "what can Y reach?" and seed from Y's border.
Implicit DAG: monotonic constraints on edge traversal eliminate cycles. Memoized DFS applies without a visited set.
State-space BFS: when (row, col) isn't sufficient state, add dimensions. Your visited set must match.

Coding these solutions quietly is the easy part. Explaining which pattern you recognized, why you reversed the BFS, or why a visited set is unnecessary because the grid is a DAG, that's what interviewers are writing down. SpaceComplexity runs voice-based mock interviews with rubric-based feedback so you practice narrating pattern recognition under pressure, not just implementing it.