Matrix Pattern: LeetCode Guide & Problems

Navigate 2D grids with DFS/BFS, rotation, spiral traversal, and flood fill.

✓ Pattern Solutions & Guides Practice Mode Enabled

7 Problem 1 Easy 6 Medium 0 Hard

Overview

Matrix problems are essentially graph problems on a 2D grid. The standard pattern is to treat each cell as a node and its 4 (or 8) neighbors as edges.

When to Use

Rotate image 90°
Spiral matrix traversal
Set matrix zeros
Search a 2D matrix
Surrounded regions
Game of life

Common Mistakes

Boundary checks — always verify r >= 0, r < rows, c >= 0, c < cols
Modifying the matrix while traversing causes bugs — use a copy or temp marker
Forgetting diagonal neighbors when 8-directional movement is needed

Complexity

Time

O(m × n)

Space

O(m × n) for BFS/DFS, O(1) for in-place tricks

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

public void bfsGrid(int[][] grid, int startR, int startC) {
    int rows = grid.length, cols = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(new int[]{startR, startC});
    visited.add(startR + "," + startC);

    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int r = curr[0], c = curr[1];
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            String key = nr + "," + nc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.contains(key)) {
                visited.add(key);
                queue.offer(new int[]{nr, nc});
            }
        }
    }
}

Problems (7)

Hide completed

Problem	Difficulty	Companies	Freq	Solution
Rotate Image #Array #Matrix #Math	Medium	AmazonMicrosoft +1	High	Solution
Spiral Matrix #Array #Matrix #Simulation	Medium	AmazonMicrosoft +2	High	Solution
Set Matrix Zeroes #Array #Matrix	Medium	AmazonMicrosoft +1	High	Solution
Maximal Square #Array #Dynamic Programming #Matrix	Medium	FacebookAmazon +2	High	Solution
Game of Life #Array #Matrix #Simulation	Medium	GoogleAmazon +2	Medium	Solution
Search a 2D Matrix II #Array #Binary Search #Divide and Conquer	Medium	AmazonApple +2	High	Solution
Count Negative Numbers in a Sorted Matrix #Array #Binary Search #Matrix	Easy	AmazonGoogle	Medium	Solution

🧠

Mastering the Matrix Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Matrix pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Matrix, the target time complexity is typically O(m × n) while maintaining an auxiliary space complexity of O(m × n) for BFS/DFS, O(1) for in-place tricks. Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.