Matrix & 2D Grid Problems: Traversal, Rotation, Islands & DP

Matrix questions are a large share of what shows up in coding rounds, from "print this matrix in spiral order" in a service-company test to "rotting oranges" or "minimum path sum" at Amazon or Flipkart. They feel different from one another, but they're built from a small set of reusable moves. Most bugs in grid code aren't conceptual. They're index errors: swapped rows and columns, missing bounds checks, a boundary that shrinks one step too far.

This guide groups the common problems by the move they use, gives Python and Java code for each, and points out the specific index traps. The final section is a checklist for presenting grid solutions in an interview.

The Grid Toolkit: Directions, Bounds and Visited Cells

Write these once and reuse them in every grid problem:

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]          # down, up, right, left
# add (1,1), (1,-1), (-1,1), (-1,-1) for 8-directional problems

def neighbours(r, c, R, C):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

static boolean inBounds(int r, int c, int R, int C) {
    return r >= 0 && r < R && c >= 0 && c < C;
}

A few conventions that prevent bugs:

• Name things R and C (or m and n) and never mix them. matrix[r][c] with r in [0, R) and c in [0, C). Most "works on square matrices, fails on rectangles" bugs come from using one length for both.
• Flatten when useful: cell (r, c) ↔ index r * C + c; back with divmod(i, C). This helps for binary search, union-find and storing cells in a set.
• Mark visited when you enqueue, not when you dequeue in BFS. Otherwise the same cell can enter the queue many times.
• Every grid traversal is O(R·C) if each cell is processed a constant number of times. Say this as your complexity.

Spiral Matrix and Other Traversal Orders

Spiral Matrix (LeetCode 54)

Keep four boundaries and peel the matrix layer by layer: top row, right column, bottom row (reversed), left column (reversed), shrinking each boundary as you finish it.

def spiralOrder(matrix):
    res = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            res.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            res.append(matrix[r][right])
        right -= 1
        if top <= bottom:                       # a row is left to walk back
            for c in range(right, left - 1, -1):
                res.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:                       # a column is left to walk up
            for r in range(bottom, top - 1, -1):
                res.append(matrix[r][left])
            left += 1
    return res

public List<Integer> spiralOrder(int[][] m) {
    List<Integer> res = new ArrayList<>();
    int top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) res.add(m[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) res.add(m[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) res.add(m[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) res.add(m[r][left]);
            left++;
        }
    }
    return res;
}

Dry run on a 3×4 matrix:

The two if guards are the whole difficulty. Without them, a matrix with an odd number of rows (like this one) prints the middle row twice, once forwards and once backwards. Spiral Matrix II (59) runs the same loop but writes 1, 2, 3, … into an n×n grid instead of reading.

Diagonal traversal

Cells on the same anti-diagonal share r + c; cells on the same main diagonal share r − c. That fact turns diagonal problems into grouping problems: Diagonal Traverse (498) groups by r + c and reverses alternate groups; Toeplitz Matrix (766) checks that each cell equals its upper-left neighbour; the N-Queens diagonal checks use the same two keys.

Rotate Image: 90 Degrees In Place (LeetCode 48)

Rotating clockwise sends cell (r, c) to (c, n−1−r). That map is the composition of two simple operations: transpose (r, c) → (c, r), then reverse each row (c, r) → (c, n−1−r).

def rotate(matrix):
    n = len(matrix)
    for i in range(n):                       # transpose: swap across the diagonal
        for j in range(i + 1, n):            # j > i, or you'd swap twice
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:                       # reverse each row
        row.reverse()

public void rotate(int[][] m) {
    int n = m.length;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t;
        }
    for (int[] row : m)
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int t = row[l]; row[l] = row[r]; row[r] = t;
        }
}

The alternative is rotating four cells at a time, layer by layer, which is a single pass but much easier to get wrong under pressure. If the interviewer asks for it, the four cells are (i, j), (j, n−1−i), (n−1−i, n−1−j) and (n−1−j, i), for layers i < n/2 and j from i to n−2−i. Rotation in place only works for square matrices; a rectangular matrix needs a new R×C → C×R array.

Set Matrix Zeroes with O(1) Extra Space (LeetCode 73)

If a cell is 0, zero its entire row and column. The trap: zeroing as you scan creates new zeros that then wipe out more rows. The O(R + C) fix records zero rows and columns in two sets. The O(1) fix uses the first row and first column as those sets, with two flags remembering whether the first row and column themselves need zeroing.

def setZeroes(M):
    R, C = len(M), len(M[0])
    first_row = any(M[0][c] == 0 for c in range(C))
    first_col = any(M[r][0] == 0 for r in range(R))
    for r in range(1, R):                    # record markers
        for c in range(1, C):
            if M[r][c] == 0:
                M[r][0] = 0
                M[0][c] = 0
    for r in range(1, R):                    # apply markers to the interior
        for c in range(1, C):
            if M[r][0] == 0 or M[0][c] == 0:
                M[r][c] = 0
    if first_row:
        for c in range(C):
            M[0][c] = 0
    if first_col:
        for r in range(R):
            M[r][0] = 0

The order matters: the interior is updated using the markers before the first row and column are overwritten. It's a good example of a problem where the interviewer is testing whether you can reuse the input as scratch space safely.

Searching a Sorted 2D Matrix

Fully sorted matrix (LeetCode 74): one binary search

Rows are sorted and each row starts after the previous one ends, so reading row by row gives one sorted array of R·C elements. Binary search over indices and convert with divmod.

def searchMatrix(M, target):
    R, C = len(M), len(M[0])
    lo, hi = 0, R * C - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        v = M[mid // C][mid % C]            # flatten index -> (row, col)
        if v == target:
            return True
        if v < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

O(log(R·C)). Note it's mid // C and mid % C, dividing by the number of columns. Using R here is a classic bug that passes on square test cases.

Rows and columns sorted independently (LeetCode 240): staircase search

Start at the top-right corner. It's the largest in its row and smallest in its column, so every comparison eliminates a whole row or column.

public boolean searchMatrix(int[][] M, int target) {
    int r = 0, c = M[0].length - 1;
    while (r < M.length && c >= 0) {
        if (M[r][c] == target) return true;
        if (M[r][c] > target) c--;     // everything below in this column is bigger
        else r++;                      // everything left in this row is smaller
    }
    return false;
}

O(R + C). Starting from the top-left doesn't work: both moves (right and down) increase the value, so a comparison doesn't tell you which way to go. This is the same elimination argument as Two Sum II on a sorted array.

Kth Smallest Element in a Sorted Matrix (LeetCode 378)

Binary search on the value, not the index. For a candidate value mid, count cells ≤ mid with the staircase walk in O(n). The smallest value whose count reaches k is the answer.

def kthSmallest(M, k):
    n = len(M)
    lo, hi = M[0][0], M[-1][-1]
    while lo < hi:
        mid = (lo + hi) // 2
        count, c = 0, n - 1
        for r in range(n):                   # staircase count of cells <= mid
            while c >= 0 and M[r][c] > mid:
                c -= 1
            count += c + 1
        if count < k:
            lo = mid + 1
        else:
            hi = mid
    return lo

O(n·log(max − min)). The returned value is guaranteed to be in the matrix because it's the smallest value with count ≥ k. This "binary search on the answer plus a monotone counting function" pattern is explained in depth in binary search on answer problems.

Flood Fill, Number of Islands and Connected Regions

A grid is a graph: cells are nodes, adjacent cells are edges. Connectivity questions are therefore DFS/BFS questions, just without an explicit adjacency list.

Flood Fill (LeetCode 733)

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:                 # otherwise recursion never terminates
        return image
    R, C = len(image), len(image[0])

    def dfs(r, c):
        if not (0 <= r < R and 0 <= c < C) or image[r][c] != old:
            return
        image[r][c] = color          # recolouring doubles as "visited"
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)

    dfs(sr, sc)
    return image

The early return when the colour is unchanged is the bug interviewers wait for. Without it, recoloured cells still match old and the DFS loops forever.

Number of Islands (LeetCode 200)

Scan every cell; each time you hit unvisited land, count an island and flood it so its cells aren't counted again. Here's the BFS version, which avoids deep recursion:

public int numIslands(char[][] grid) {
    int R = grid.length, C = grid[0].length, islands = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Deque<int[]> q = new ArrayDeque<>();
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
            if (grid[r][c] != '1') continue;
            islands++;
            grid[r][c] = '0';                 // mark on enqueue
            q.add(new int[]{r, c});
            while (!q.isEmpty()) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int nr = cur[0] + d[0], nc = cur[1] + d[1];
                    if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        q.add(new int[]{nr, nc});
                    }
                }
            }
        }
    return islands;
}

O(R·C) time; the queue holds at most O(min(R, C)) cells in a typical BFS frontier but O(R·C) in the worst case. A recursive DFS on a 1000×1000 all-land grid could recurse up to a million frames deep, which will overflow in Python and likely in Java. The Number of Islands deep dive also covers the union-find approach, which matters for the "islands added one at a time" follow-up (LeetCode 305).

Variations on the same flood

"Start from the border and work inward" (Surrounded Regions, Pacific Atlantic, Closed Islands) is the single most useful trick in this family. When a condition is about reaching the edge, reverse the search so it starts from the edge.

Shortest Paths in a Grid with BFS

BFS visits cells in order of distance from the start, so the first time it reaches a cell is via a shortest path, as long as every move costs the same. That's the tool for "minimum steps" questions.

Shortest Path in Binary Matrix (LeetCode 1091)

from collections import deque

def shortestPathBinaryMatrix(grid):
    n = len(grid)
    if grid[0][0] or grid[n - 1][n - 1]:
        return -1
    q = deque([(0, 0, 1)])                   # row, col, path length in cells
    grid[0][0] = 1                           # mark visited
    while q:
        r, c, d = q.popleft()
        if (r, c) == (n - 1, n - 1):
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):            # 8 directions
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    q.append((nr, nc, d + 1))
    return -1

Multi-source BFS

When there are many starting points, put them all in the queue at distance 0. BFS then computes each cell's distance to its nearest source in one pass. That solves Rotting Oranges (994) (all rotten oranges start together, the answer is the number of layers), 01 Matrix (542) (distance to nearest 0) and Walls and Gates (286). Running a separate BFS from every source would be O((R·C)²); multi-source is O(R·C). The Rotting Oranges walkthrough traces it layer by layer.

When moves have different costs, BFS no longer works. Costs of 0 or 1 → 0-1 BFS with a deque. General non-negative costs, as in Path With Minimum Effort (1631) → Dijkstra with a heap. Both are in the graph BFS and DFS guide.

Grid Dynamic Programming: Paths, Costs and Squares

When you can only move right and down, there are no cycles, and each cell's answer depends only on the cell above and the cell to the left. Fill the table row by row and the dependencies are always ready.

Minimum Path Sum (LeetCode 64)

def minPathSum(grid):
    R, C = len(grid), len(grid[0])
    dp = [float('inf')] * C
    dp[0] = 0
    for r in range(R):
        for c in range(C):
            if c == 0:
                dp[c] += grid[r][c]                       # only from above
            else:
                dp[c] = min(dp[c], dp[c - 1]) + grid[r][c]  # above vs left
    return dp[-1]

public int minPathSum(int[][] g) {
    int R = g.length, C = g[0].length;
    int[] dp = new int[C];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            dp[c] = (c == 0 ? dp[c] : Math.min(dp[c], dp[c - 1])) + g[r][c];
    return dp[C - 1];
}

Why does one array work? Before updating, dp[c] still holds the previous row's value (the cell above), and dp[c−1] was just updated for the current row (the cell to the left). In the first row, "above" is infinity, so only the left neighbour counts. O(R·C) time, O(C) space.

Unique Paths II with obstacles (LeetCode 63)

def uniquePathsWithObstacles(grid):
    C = len(grid[0])
    dp = [0] * C
    dp[0] = 1
    for row in grid:
        for c in range(C):
            if row[c] == 1:
                dp[c] = 0                  # no paths through an obstacle
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[-1]

Maximal Square (LeetCode 221)

Let dp[r][c] be the side of the largest all-'1' square with its bottom-right corner at (r, c). A square of side k there needs squares of side k−1 ending above, to the left and diagonally up-left, so:

dp[r][c] = 1 + min(dp[r−1][c], dp[r][c−1], dp[r−1][c−1]) if the cell is '1', else 0

public int maximalSquare(char[][] M) {
    int R = M.length, C = M[0].length, best = 0;
    int[][] dp = new int[R + 1][C + 1];          // padded: no edge checks
    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            if (M[r - 1][c - 1] == '1') {
                dp[r][c] = 1 + Math.min(dp[r - 1][c - 1],
                                        Math.min(dp[r - 1][c], dp[r][c - 1]));
                best = Math.max(best, dp[r][c]);
            }
    return best * best;
}

Other grid DPs worth knowing: Triangle (120) (bottom-up is cleanest), Dungeon Game (174) (fill from the bottom-right because the constraint is about minimum health needed going forward), Cherry Pickup (741) (two walkers moving simultaneously, state (step, r1, r2)), and Longest Increasing Path in a Matrix (329) (all four directions, so it's DFS with memoisation rather than row-by-row DP, which only works because strictly increasing paths can't cycle). For submatrix sums, use a 2D prefix sum instead; see prefix sum problems.

Grid Problems in Interviews: Checklist and Common Mistakes

Ask before you code

• Is the grid rectangular? Can it be empty (R = 0 or C = 0)?
• Four directions or eight? Can I move diagonally?
• May I modify the input to mark visited cells?
• For DP: which moves are allowed? Only right/down, or all four?
• How large is the grid? (Decides recursion vs. explicit stack.)

Pick the technique

That last one deserves emphasis because it's silent: [[0] * C] * R looks right, but writing to one row writes to all of them. Use [[0] * C for _ in range(R)].

Practice order

1. Simulation: 54 Spiral Matrix, 59 Spiral Matrix II, 48 Rotate Image, 73 Set Matrix Zeroes, 498 Diagonal Traverse.
2. Search: 74 Search a 2D Matrix, 240 Search a 2D Matrix II, 378 Kth Smallest in Sorted Matrix.
3. Flood fill: 733, 200, 695, 130, 417.
4. BFS: 1091, 994, 542, 1631.
5. DP: 62, 63, 64, 221, 120, 329.

Around 25 problems. Once the toolkit at the top of this page is automatic, most new grid problems turn out to be one of these moves with a small twist.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.