Top 12 Matrix Interview Problems: Every Pattern You Need

You're 15 minutes into an interview. Your interviewer shares their screen. There is a grid. Every cell holds a zero, a one, or a letter. You feel the specific dread that only a 2D array can produce.

Matrix problems feel more exotic than they are. The 12 below cover every variation that shows up in real loops, ordered by difficulty so each one builds on the last. Work through all of them and the grid stops being intimidating. It becomes a graph wearing a disguise.

The One Insight That Makes Everything Click

A matrix is a graph. Cell (r, c) has up to four neighbors: (r+1, c), (r-1, c), (r, c+1), (r, c-1). The edges are implicit in the coordinate arithmetic, not written out in an adjacency list anyone gave you. Once you see it that way, flood fill and BFS become the same tools you already know, just applied to row-column pairs instead of node IDs.

Nearly every matrix problem belongs to one of five families: flood fill, boundary simulation, 2D dynamic programming, binary search, or in-place transformation. Name the family before you write a single line. This is worth saying out loud, because naming the pattern is also one of the first things your interviewer is scoring.

1. Flood Fill (LeetCode 733, Easy)

Pattern: DFS from a seed cell.

Start at one pixel. Change its color. Recursively change every 4-connected neighbor with the same original color. This is the flood fill algorithm in its purest form and the right place to start.

The critical edge case: if the new color equals the original color, return immediately. Skip this check and the DFS recurses forever. This particular gotcha has ended interviews.

def floodFill(image, sr, sc, color):
    original = image[sr][sc]
    if original == color:
        return image

    def dfs(r, c):
        if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]):
            return
        if image[r][c] != original:
            return
        image[r][c] = color
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    dfs(sr, sc)
    return image

Time: O(m×n). Space: O(m×n) call stack.

2. Number of Islands (LeetCode 200, Medium)

Pattern: Count connected components via DFS.

The outer loop finds undiscovered components. The DFS sinks each one by overwriting '1' with '0' as it goes. No visited set needed because mutation is the visited marker. Using the input array as scratch space is the kind of observation interviewers like writing down in their notes.

What separates this from Flood Fill: here you count how many times the outer loop fires a DFS, not what the DFS does internally.

def numIslands(grid):
    count = 0

    def dfs(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

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

    return count

Time: O(m×n). Space: O(m×n).

3. Spiral Matrix (LeetCode 54, Medium)

Pattern: Boundary simulation.

Traverse in spiral order by shrinking four boundaries (top, bottom, left, right) after consuming each edge. Every candidate draws the spiral on paper and thinks they have it. Then the off-by-ones arrive in the bottom and left passes of non-square matrices.

The boundary-shrink approach is cleaner than tracking a direction variable explicitly. Check top <= bottom and left <= right before processing the bottom and left passes, or you'll double-count center rows and columns.

def spiralOrder(matrix):
    result = []
    top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1

    while top <= bottom and left <= right:
        for c in range(left, right+1):
            result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom+1):
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left-1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top-1, -1):
                result.append(matrix[r][left])
            left += 1

    return result

Time: O(m×n). Space: O(1) excluding output.

4. Search a 2D Matrix (LeetCode 74, Medium)

Pattern: Binary search via coordinate transform.

Each row is sorted and the first element of each row is greater than the last of the previous. The whole matrix is a sorted array folded into 2D. Map a 1D midpoint mid to (mid // cols, mid % cols) and you have standard binary search.

Most candidates reach for the two-pointer staircase approach. That's O(m+n). The coordinate transform gets you O(log(m×n)). One line of index arithmetic buys you a full log factor. If you have time, mention both and explain the tradeoff.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        elif value < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return False

Time: O(log(m×n)). Space: O(1).

5. Set Matrix Zeroes (LeetCode 73, Medium)

Pattern: In-place marking with boundary state.

If any cell is zero, zero its entire row and column. The O(1) space trick: use the first row and first column as flag arrays. Before using them as flags, record whether they themselves need zeroing, because you are about to corrupt them.

Always mark first, apply second. Mix both in one pass and the flags you're reading get overwritten mid-traversal. The two-pass structure is load-bearing.

def setZeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row = any(matrix[0][c] == 0 for c in range(cols))
    first_col = any(matrix[r][0] == 0 for r in range(rows))

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    if first_row:
        for c in range(cols): matrix[0][c] = 0
    if first_col:
        for r in range(rows): matrix[r][0] = 0

Time: O(m×n). Space: O(1).

6. Rotate Image (LeetCode 48, Medium)

Pattern: Decompose into transpose then row-reverse.

Rotate 90 degrees clockwise in-place. You could track every cell's destination directly, or you could notice that rotation decomposes cleanly into two simpler operations: transpose (swap rows and columns), then reverse each row. Two passes you can verify independently, composed into a rotation that would be painful to implement directly.

Complex geometric transformations almost always decompose into simpler steps. Verify each step independently before combining.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i+1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

Time: O(n²). Space: O(1).

7. Unique Paths (LeetCode 62, Medium)

Pattern: 2D dynamic programming, base case on boundaries.

Count paths from top-left to bottom-right moving only right or down. Recurrence: dp[r][c] = dp[r-1][c] + dp[r][c-1]. The entire top row and left column are 1 (only one way to reach any cell on those edges).

The space optimization collapses 2D DP to 1D: you only need the previous row, so a single array updated left-to-right suffices. Say this before you code it. The interviewer will notice.

def uniquePaths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c-1]
    return dp[n-1]

Time: O(m×n). Space: O(n).

8. Word Search (LeetCode 79, Medium)

Pattern: DFS with backtracking on a grid.

Find if a word exists as a path of adjacent cells (4-directional, no reuse). Start a DFS at every candidate cell. Mark cells visited by mutating them to '#' on the way in and restoring on the way back. The mutation-and-restore pattern is the same one in every backtracking problem.

If index == len(word), you've matched every character. Return True immediately without checking the cell value.

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        temp, board[r][c] = board[r][c], '#'
        found = (dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or
                 dfs(r,c+1,i+1) or dfs(r,c-1,i+1))
        board[r][c] = temp
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Time: O(m×n×4^L). Space: O(L).

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

Pattern: Reverse multi-source BFS from each border.

Find cells where water can flow to both oceans. Simulating water flow downhill from every cell is O(m²×n²). Flip the direction instead: flood uphill from the Pacific border (top and left edges), then uphill from the Atlantic border (bottom and right edges). The intersection is the answer.

When "simulate from each cell" is too slow, start from destinations and flood backward. This reversal is the whole insight, and saying it out loud before you start coding is exactly how you get full credit for problem-solving.

def pacificAtlantic(heights):
    rows, cols = len(heights), len(heights[0])

    def bfs(starts):
        visited = set(starts)
        queue = list(starts)
        while queue:
            r, c = queue.pop()
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r+dr, c+dc
                if (0<=nr<rows and 0<=nc<cols and (nr,nc) not in visited
                        and heights[nr][nc] >= heights[r][c]):
                    visited.add((nr, nc))
                    queue.append((nr, nc))
        return visited

    pacific = {(0,c) for c in range(cols)} | {(r,0) for r in range(rows)}
    atlantic = {(rows-1,c) for c in range(cols)} | {(r,cols-1) for r in range(rows)}
    return list(bfs(pacific) & bfs(atlantic))

Time: O(m×n). Space: O(m×n).

10. Maximal Square (LeetCode 221, Medium)

Pattern: 2D DP with a non-obvious recurrence.

Find the largest all-'1' square. At each cell, dp[r][c] is the side length of the largest such square with its bottom-right corner at (r, c). The recurrence: dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1 when the cell itself is '1'. See dynamic programming problems for the broader pattern category.

Deriving the recurrence is the hard part. The three neighbors represent squares above, to the left, and diagonally above-left. The min determines how far you can extend in all directions simultaneously. Candidates who try to derive this cold, mid-interview, usually don't finish.

def maximalSquare(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dp = [[0]*(cols+1) for _ in range(rows+1)]
    max_side = 0

    for r in range(1, rows+1):
        for c in range(1, cols+1):
            if matrix[r-1][c-1] == '1':
                dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
                max_side = max(max_side, dp[r][c])

    return max_side * max_side

Time: O(m×n). Space: O(m×n), reducible to O(n) with a rolling row.

11. Game of Life (LeetCode 289, Medium)

Pattern: In-place state transition via integer encoding.

Apply Conway's Game of Life rules without extra space. The problem: updating a cell corrupts information its neighbors still need. The fix: encode the transition in the value itself. Use 2 for live-to-dead and 3 for dead-to-live, then do a second pass to decode. Count a cell as "currently alive" if its value is 1 or 2. You get to code cellular automata in a coding interview. This is peak CS.

This integer-encoding trick generalizes to any problem where you need to track "state before the update" without copying the array. Not just Conway.

def gameOfLife(board):
    rows, cols = len(board), len(board[0])

    def live_neighbors(r, c):
        count = 0
        for dr in range(-1, 2):
            for dc in range(-1, 2):
                if dr == dc == 0:
                    continue
                nr, nc = r+dr, c+dc
                if 0<=nr<rows and 0<=nc<cols and board[nr][nc] in (1, 2):
                    count += 1
        return count

    for r in range(rows):
        for c in range(cols):
            n = live_neighbors(r, c)
            if board[r][c] == 1 and (n < 2 or n > 3):
                board[r][c] = 2
            elif board[r][c] == 0 and n == 3:
                board[r][c] = 3

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == 2: board[r][c] = 0
            elif board[r][c] == 3: board[r][c] = 1

Time: O(m×n). Space: O(1).

12. Maximal Rectangle (LeetCode 85, Hard)

Pattern: Reduce 2D problem to repeated 1D histogram problems.

Find the largest rectangle of all '1's. This is the hardest matrix problem in a standard interview loop, and it reduces entirely to a problem you should already know. Build a heights array where heights[c] at each row is the count of consecutive '1's above (including the current cell) in column c. Then run the O(n) monotonic stack "Largest Rectangle in Histogram" algorithm on each row. See monotonic stack problems for that subroutine.

def maximalRectangle(matrix):
    if not matrix:
        return 0
    cols = len(matrix[0])
    heights = [0] * cols
    max_area = 0

    def largest_in_histogram(h):
        stack, area = [], 0
        for i, val in enumerate(h + [0]):
            while stack and h[stack[-1]] > val:
                height = h[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                area = max(area, height * width)
            stack.append(i)
        return area

    for row in matrix:
        for c in range(cols):
            heights[c] = heights[c] + 1 if row[c] == '1' else 0
        max_area = max(max_area, largest_in_histogram(heights))

    return max_area

Time: O(m×n). Space: O(n).

The reduction is everything. Each row generates a histogram. The largest rectangle in that histogram is a candidate answer. You either walked in knowing the histogram subroutine, or you didn't. There is no improvising it in 45 minutes.

Pattern Map

Problem	Pattern	Difficulty
Flood Fill	DFS seed traversal	Easy
Number of Islands	Connected components	Medium
Spiral Matrix	Boundary simulation	Medium
Search a 2D Matrix	Binary search	Medium
Set Matrix Zeroes	In-place marking	Medium
Rotate Image	Transpose + reverse	Medium
Unique Paths	2D DP	Medium
Word Search	DFS + backtracking	Medium
Pacific Atlantic	Reverse multi-source BFS	Medium
Maximal Square	2D DP recurrence	Medium
Game of Life	Integer state encoding	Medium
Maximal Rectangle	Histogram + monotonic stack	Hard

The Two Problems That End Interviews

Problems 10 and 12 cause the most failures in real loops. Maximal Square looks like a greedy problem. Every instinct says there should be a clean spatial formula. There isn't. Maximal Rectangle looks impossible without knowing the histogram reduction, because it basically is.

For problems 1 and 2, the variants worth practicing are Max Area of Island (LeetCode 695) and Surrounded Regions (LeetCode 130). Surrounded Regions inverts the flood fill direction: mark what cannot be captured from the border, then flip everything else. The logic inverts but the mechanics are identical. Check the full grid problems list for those.

One thing this problem list cannot train: narrating your traversal order out loud while you write. Which cells you visit, in what order, and why the boundary conditions hold. That's what gets scored in a live interview. SpaceComplexity runs voice-based mock interviews with rubric-based feedback on communication alongside correctness. Worth running through a few matrix problems there before your actual loop.