A matrix is just a graph wearing a grid costume. Once you see each cell as a node with up-to-four neighbors, the patterns collapse into three moves: coordinate arithmetic, in-place transforms, and boundary simulation.
A 2-D grid is almost never “just an array of arrays” — it's either an implicit graph (every cell wired to its neighbours) or a canvas for careful coordinate bookkeeping. Decide which, and the problem stops being about the grid and starts being about edges or index math.
Stop seeing grid[r][c] as a number in a table. See it as a node in a graph, connected by invisible edges to the cells directly above, below, left, and right. The grid never printedthose edges — but they are always there, and almost every “hard” matrix problem is really a graph problem that forgot to mention it.
Once cells are nodes, your whole graph toolkit applies unchanged: DFS / flood-fill to paint a connected region, BFS to find shortest steps (each ring of the BFS is one more step away), and a visited set to avoid walking in circles. The grid just happens to be a graph with a very regular, predictable adjacency.
Every cell has the same shape of connection — a little plus of up-to-four neighbours. That regularity is why one tiny directions array drives every traversal:
A cell at (r,c) is wired to its 4 orthogonal neighbours:
(r-1, c)
│
(r, c-1) ──── ( r , c ) ──── (r, c+1)
│
(r+1, c)
┌────┬────┬────┐ dirs = [[-1, 0], ← up
│ │ ▲ │ │ [ 1, 0], ← down
├────┼────┼────┤ [ 0,-1], ← left
│ ◄ │ ● │ ► │ [ 0, 1]] ← right
├────┼────┼────┤
│ │ ▼ │ │ ● = current cell (r,c)
└────┴────┴────┘ ▲▼◄► = the 4 edges out of itRun a DFS from a land cell and it floods outward across 1→1 edges, stopping dead at water and the border. Each separate flood is one island:
grid DFS from the top-left 1 floods its whole island: 1 1 0 0 1 (1)(1) 0 0 1 # = filled this island 1 0 0 0 1 ──► (1) 0 0 0 1 0 = water (edge: blocked) 0 0 1 1 0 0 0 1 1 0 the lone 1s are SEPARATE 0 0 1 0 0 0 0 1 0 0 islands (no path of 1s) The flood only crosses 1→1 edges and stops at 0s and the grid border. Count islands = count how many times you START a fresh flood.
Faced with a fresh 2-D problem, climb these rungs in order. The first question that answers “yes” tells you which of the three matrix moves you need:
dirs array and a visited mechanism.out[c][n-1-r] = in[r][c]), then realize it as a sequence of in-place swaps. No second matrix.grid[nr][nc], assert 0 <= nr < rows and 0 <= nc < cols. This is the single most common grid bug.[[1,0],[-1,0],[0,1],[0,-1]] plus one bounds check solves islands, flood fill, word search, rotting oranges, walls-and-gates, and shortest path — they are the same loop with a different cell test.Before writing the recursion, say the traversal contract out loud as one sentence: “I only step onto a neighbour that is in bounds and not yet visited, and the first thing I do on arrival is mark it.” Marking before recursing is what stops the flood from spilling back onto itself forever.
walk(grid): # treat the grid as a graph
rows, cols = size of grid
dirs = [up, down, left, right] # the 4 edges out of a cell
visit(r, c):
if (r, c) out of bounds: # 0<=r<rows AND 0<=c<cols
return # ← bound EVERY access
if visited or fails test: # water, wall, already seen
return
mark (r, c) visited # a flag, or mutate the cell
for (dr, dc) in dirs: # step to each neighbour
visit(r + dr, c + dc)
for every cell (r, c): # kick off a walk anywhere
visit(r, c) # fresh start = one regionNotice the order: bounds → visited/cell test → mark → recurse on neighbours. Every island, flood-fill, and word-search solution is this skeleton with a different cell test and a different thing happening at the “mark” step.
The other half of matrix problems isn't graphs at all — it's pure coordinate arithmetic. A rotation, transpose, or spiral is just a rule for where each cell's value should end up. The trick is to express that rule as the composition of a couple of simple, reversible moves you can do with swaps:
Rotate 90° clockwise is TWO index remaps, both in place:
start transpose reverse each row
1 2 3 1 4 7 7 4 1
4 5 6 ──► 2 5 8 ──► 8 5 2
7 8 9 3 6 9 9 6 3
(mirror over \ ) (flip left↔right)
result[c][n-1-r] = start[r][c]. Decompose the remap into two
moves you can each do with simple swaps — no scratch matrix.Rotating 90° clockwise looks intimidating until you see it as transpose, then reverse each row. Each step is a clean in-place operation; chaining them gives the full remap with zero extra memory. Spiral order is the same spirit — four shrinking boundaries that, together, enumerate the cells in the right sequence:
Visit order spirals inward, peeling one ring per pass:
1 → 2 → 3 → 4 top row (left → right)
↓ right col (top → bottom)
12 → 13 → 14 5 bottom (right → left)
↑ ↓ ↓ left col (bottom → top)
11 16 ← 15 6 then the inner ring repeats
↑ ↓
10 ← 9 ← 8 ← 7
Four boundaries close in: top↓ bottom↑ left→ right←
When they cross, every cell has been emitted exactly once.When a problem screams “O(1) extra space,” the answer is usually: store your bookkeeping inside the grid itself. You already own m × n cells — borrow a few as flags instead of allocating a parallel structure.
grid[i][0]records “row i must be zeroed” and grid[0][j] records the column. Save two booleans for the borders themselves, then apply.visited set, overwrite each visited 1 with 0 (or a sentinel). The grid mutation is the visited mark.Every cell (r, c) has up to four neighbors: (r-1,c), (r+1,c), (r,c-1), (r,c+1). Encode them as a direction array and iterate:
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
for (const [dr,dc] of dirs) {
const nr = r+dr, nc = c+dc;
if (nr>=0 && nr<m && nc>=0 && nc<n) { /* valid */ }
}Bounds-check every neighbor before visiting — forgetting this is the single most common runtime error on grid problems. Converting between a 1-D index and a 2-D coordinate: row = idx / n | 0, col = idx % n.
Two classic O(1)-space matrix mutations to internalize:
[i][j] with [j][i], upper triangle only so you don't double-swap), then reverse each row. Two O(n²) passes, zero extra cells.Some problems require visiting cells in a non-trivial order — spiral being the canonical example. Maintain four boundary variables top, bottom, left, right and shrink them inward after each edge is consumed.
The subtle bug: after consuming the top row and the right column, the bottom-row and left-column traversals need their own top <= bottom / left <= right guards. Without those guards a single-row or single-column matrix emits cells twice.
The same shrinking-boundary idea applies to any "process the perimeter, then repeat on the inner sub-matrix" pattern (e.g. rotating a matrix layer by layer).
Reach for matrix patterns when the problem hands you a 2-D grid and asks you to transform it in place, traverse in a specific order, or explore connected regions. The tell is always a 2-D index and cells that interact with their neighbors.
| "rotate the image in place" / 90° rotation | transpose (upper triangle only) then reverse each row |
| "set entire row and column to zero" in O(1) space | use first row & col as flag markers; save two border booleans |
| "traverse in spiral order" | shrinking top/bottom/left/right boundaries, peel one ring per iteration |
| "flood fill / count islands / region boundaries" | BFS or DFS on 4-directional neighbors (also lives in the Graphs category) |
| "search for a value in a row-sorted / column-sorted matrix" | binary search — see the Binary Search category for the full pattern |
| "shortest path / minimum steps on a grid" | BFS from source, level = steps; treat cells as graph nodes |
| neighbors, adjacency, or reachability on a 2-D board | direction array + bounds check + visited set or in-place mark |
When → An n×n matrix must be rotated 90° clockwise without allocating a second matrix. The two-step trick: transpose (swap upper triangle only), then reverse every row.
function rotate(matrix: number[][]): void {
const n = matrix.length;
// Step 1 — transpose: swap matrix[i][j] with matrix[j][i].
// Only iterate the upper triangle (j > i) to avoid double-swapping.
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
// Step 2 — reverse each row.
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
}j = i + 1, not j = 0. If you start at 0 you swap [i][j] with [j][i], then swap them back — net effect: nothing changes.When → Any cell containing zero must zero out its entire row and column. O(1) extra space by recycling the first row and column as flag arrays.
function setZeroes(matrix: number[][]): void {
const m = matrix.length, n = matrix[0].length;
// Remember whether row-0 / col-0 themselves contain a zero.
let firstRowZero = matrix[0].some(v => v === 0);
let firstColZero = matrix.some(r => r[0] === 0);
// Use row-0 and col-0 as markers for the rest of the matrix.
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0; // flag the row
matrix[0][j] = 0; // flag the column
}
}
}
// Apply flags (skip row-0 / col-0 for now).
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
}
}
// Handle the border rows/columns using the booleans saved above.
if (firstRowZero) matrix[0].fill(0);
if (firstColZero) { for (let i = 0; i < m; i++) matrix[i][0] = 0; }
}matrix[0][j] while still scanning the interior, a later cell in that column sees a false flag and gets wrongly zeroed. Scan interior first; apply borders last using the saved booleans.When → Visit every cell in clockwise spiral order. Maintain four boundary pointers and shrink them inward. Guard mid-loop before the bottom and left passes.
function spiralOrder(matrix: number[][]): number[] {
const result: number[] = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// → traverse top row
for (let c = left; c <= right; c++) result.push(matrix[top][c]);
top++;
// ↓ traverse right column
for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
right--;
// ← traverse bottom row (guard: still a distinct row)
if (top <= bottom) {
for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
bottom--;
}
// ↑ traverse left column (guard: still a distinct column)
if (left <= right) {
for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
left++;
}
}
return result;
}top++ and right--, check top <= bottom before the bottom-row pass and left <= right before the left-column pass. A matrix with a single row or single column will otherwise emit cells twice.The inner loop of the transpose step must start at j = i + 1. Starting at j = 0 swaps every pair twice and leaves the matrix unchanged — a silent, maddening no-op.
If you naively zero rows and columns as you encounter zeros, new zeros in those rows/columns trigger more zeroing on the next iteration. Always collect all flag positions first (or use the first-row/col markers), then apply them in a second pass.
After consuming the top row (top++) and right column (right--), you must re-check top <= bottom before traversing the bottom row, and left <= right before traversing the left column. Skipping these guards duplicates cells when the matrix is a single row or single column.
Every BFS/DFS step on a grid must validate that nr and nc are in range before indexing. Accessing matrix[-1][c] in JavaScript returns undefined (not a crash), which silently corrupts visited checks and produces wrong answers.