Blind 75 — Matrix Pattern Guide

How to Identify a “Matrix” Problem

Interview Triggers

• Input is int[][] or char[][]
• “In-place” modifications to the matrix
• “Spiral”, “rotate”, “transpose”
• “Search a word on the board” (DFS)
• “Set entire row/col to zero if cell is 0”

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Zero out row/column whose cell is 0 (in-place)	First row/col as markers	73
Print matrix in spiral order	Layer-by-layer / 4 boundaries	54
Rotate matrix 90° clockwise (in-place)	Transpose + reverse each row	48
Search word path on grid	DFS + backtracking	79

---

The Decision Tree

MATRIX PROBLEM
│
├─ Need O(1) extra space for marking?
│   └─ Use first row / first col as scratch → LC 73
│
├─ Need a specific traversal order?
│   ├─ Spiral (outside-in)        → 4 boundaries shrink (LC 54)
│   ├─ Rotate 90° CW             → transpose + reverse rows (LC 48)
│   └─ Diagonal / zig-zag         → custom index formulas
│
├─ Need to search / path-find?
│   ├─ Cell connectivity / count  → DFS or BFS (LC 200)
│   └─ Path with backtracking     → DFS + visited marker (LC 79)
│
└─ Need running aggregate?
    └─ Prefix-sum 2-D (range sum queries)

---

Reusable Templates

Spiral Traversal (LC 54)

int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (top <= bottom && left <= right) {
    for (int j = left; j <= right; j++) res.add(matrix[top][j]);
    top++;
    for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
    right--;
    if (top <= bottom) { for (int j = right; j >= left; j--) res.add(matrix[bottom][j]); bottom--; }
    if (left <= right) { for (int i = bottom; i >= top; i--) res.add(matrix[i][left]); left++; }
}

Rotate 90° Clockwise (LC 48)

// 1. Transpose
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
        int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t;
    }
// 2. Reverse each row
for (int i = 0; i < n; i++)
    for (int l = 0, r = n - 1; l < r; l++, r--) {
        int t = matrix[i][l]; matrix[i][l] = matrix[i][r]; matrix[i][r] = t;
    }

DFS on Grid (LC 79 / 200)

int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
boolean dfs(char[][] g, int r, int c, ... ) {
    if (r<0||c<0||r>=g.length||c>=g[0].length || visited[r][c] || !match) return false;
    visited[r][c] = true;
    for (int[] d : dirs) if (dfs(g, r+d[0], c+d[1], ...)) return true;
    visited[r][c] = false; // backtrack if needed
    return false;
}

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Set Matrix Zeroes	73	Medium	In-place markers
2	Spiral Matrix	54	Medium	Layer boundaries
3	Rotate Image	48	Medium	Transpose + reverse

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Word Search	79	Medium	DFS backtracking

---

Java Implementation Tips

• 2-D array dims: int m = matrix.length, n = matrix[0].length; — always cache both.
• Direction array int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}}; — clean way to express 4-neighbors.
• For in-place backtracking on char[][], temporarily change a cell (e.g., '#') instead of boolean[][] visited — O(1) space.
• Be careful with int[][] “rows” — rows can have different lengths (jagged arrays); use matrix[i].length if shape may vary.

---

Senior Mental Trigger

“Rotate = Transpose + Reverse. Spiral = 4 boundaries that shrink. Word search = DFS + backtrack with # marker.”