Spirals, diagonals, islands, and flood fill - moving through 2D grids without losing your place.
What the matrix traversal pattern is
Grid problems are graph problems with geometry: each cell connects to 4 (or 8) neighbors, and the craft is walking them in the required order - row scans, spirals, diagonals, boundary walks - without index chaos. The universal tools: a direction-vector array instead of four copy-pasted branches, a bounds check factored into one place, and explicit boundary variables when the shape of the walk changes as it proceeds.
The second family is in-place transformation: rotate an image, zero rows and columns, evolve game-of-life - where the challenge is not movement but updating the grid without the new values corrupting reads of the old ones.
How to recognize it
The input is a 2D array and the ask is order-specific (spiral, diagonal, boundary), region-based (islands, flood fill - DFS/BFS wearing grid clothes), search-in-structure (sorted matrix), or transformation (rotate, set zeroes). Almost every grid question decomposes into 'traverse in a disciplined order' plus 'do something per cell'.
Mental model to carry in: directions = [(-1,0),(1,0),(0,-1),(0,1)], a single inBounds(r, c) helper, and the flatten trick (cell id = r * cols + c) when a grid must feed a 1D structure like union-find.
Spiral and boundary walks
Order-specific walks are cleanest with explicit shrinking bounds: top, bottom, left, right. Walk the top row and shrink top; right column, shrink right; bottom row, shrink bottom; left column, shrink left; repeat while bounds remain valid. The two mid-loop guards (top <= bottom before the bottom row, left <= right before the left column) are what prevent double-visiting single-row or single-column leftovers - they are the entire difficulty of the problem.
pseudocode
top = 0, bottom = rows-1, left = 0, right = cols-1
while top <= bottom and left <= right:
walk left..right along row top; top += 1
walk top..bottom along column right; right -= 1
if top <= bottom:
walk right..left along row bottom; bottom -= 1
if left <= right:
walk bottom..top along column left; left += 1
In-place transformation tricks
Rotate 90 degrees clockwise = transpose, then reverse each row - two simple passes replacing fragile four-way cycle swaps. When old and new values must coexist (game of life), encode transitions with intermediate states (alive-going-dead = 2) and decode in a second pass. When marker storage is forbidden (set matrix zeroes in O(1)), commandeer the first row and column as the marker array, tracking their own fate in two booleans.
Common pitfalls
Row/column confusion: grid[r][c] means row r (vertical position), column c (horizontal). Half of all grid bugs are transposed indices - name variables r and c, never x and y.
Spiral double-visits on non-square inputs: missing the two mid-loop guards re-walks a lone row or column in reverse.
Mutating while reading: zeroing cells during the scan that decides what to zero cascades into wiping the matrix.
Bounds checks inlined differently at four call sites - factor inBounds once or one of the four will be wrong.
Rotation direction: clockwise is transpose + reverse rows; counterclockwise is transpose + reverse columns. Verify with a 2x2 before writing the loops.
Worked examples
1. Spiral matrixmedium
Return all elements of an m x n matrix in clockwise spiral order.
Model the spiral as four boundary walks over a shrinking rectangle - four bounds variables, each consumed pass tightening one of them.
Loop while top <= bottom and left <= right: top row left-to-right, right column top-to-bottom, then - only if rows remain - bottom row right-to-left, and - only if columns remain - left column bottom-to-top.
Those two conditional guards handle non-square matrices: without them a single remaining row is emitted twice, once in each direction.
O(m x n) time, O(1) beyond the output. Trace a 3x4 by hand before coding - one minute of tracing beats ten of debugging.
pseudocode
result = []
top, bottom, left, right = 0, m-1, 0, n-1
while top <= bottom and left <= right:
for c in left..right: result.append(grid[top][c]); top += 1
for r in top..bottom: result.append(grid[r][right]); right -= 1
if top <= bottom:
for c in right..left: result.append(grid[bottom][c]); bottom -= 1
if left <= right:
for r in bottom..top: result.append(grid[r][left]); left += 1
return result
Remember: Four shrinking bounds turn the spiral into straight-line walks - and the two mid-loop guards are what keep skinny matrices from double-printing.
2. Rotate image (90 degrees, in place)medium
Rotate an n x n matrix 90 degrees clockwise, in place.
Direct four-way cycle swaps work but are fiddly and error-prone under pressure. Decompose instead: rotation = transpose + reverse each row.
Transpose: swap grid[i][j] with grid[j][i] for j > i only - sweeping the full square un-transposes everything back.
Reverse each row with the standard two-pointer swap.
Verify on a 2x2: [[1,2],[3,4]] -> transpose [[1,3],[2,4]] -> reverse rows [[3,1],[4,2]]. Correct. O(n^2) time, O(1) space, and each pass is independently testable.
pseudocode
# transpose (upper triangle only)
for i in 0 .. n-1:
for j in i+1 .. n-1:
swap(grid[i][j], grid[j][i])
# reverse each row
for each row: reverse(row)
Remember: Decompose the rotation into two trivially-correct passes - transpose then reverse - instead of juggling a four-way swap.
3. Set matrix zeroes (O(1) space)medium
If a cell is 0, set its entire row and column to 0 - in place, with constant extra space.
The naive mistake: zeroing as you scan, so introduced zeros trigger more zeroing. Marking must be separated from applying.
O(m + n) marker arrays are easy; the O(1) version stores the markers IN the matrix: first row marks doomed columns, first column marks doomed rows.
Since those cells are now markers, remember the first row's and first column's own fate in two booleans before overwriting anything.
Pass 1: scan and set markers. Pass 2: zero interior cells whose row or column marker is set (iterate from index 1). Pass 3: apply the two booleans to the first row and column last.
pseudocode
firstRowZero = any zero in row 0
firstColZero = any zero in column 0
for r in 1 .. m-1, c in 1 .. n-1:
if grid[r][c] == 0:
grid[r][0] = 0; grid[0][c] = 0 # mark
for r in 1 .. m-1, c in 1 .. n-1:
if grid[r][0] == 0 or grid[0][c] == 0:
grid[r][c] = 0 # apply
if firstRowZero: zero row 0
if firstColZero: zero column 0
Remember: Borrow the first row and column as your marker arrays - after safeguarding their own fate in two booleans - and always separate marking from applying.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Why use a directions array like [(-1,0),(1,0),(0,-1),(0,1)] instead of four explicit neighbor branches?
It is faster at runtime
✓ One loop with one shared bounds check replaces four near-duplicate code paths - and generalizes to 8 directions by extending the array
It uses less memory
Branches cannot handle negative indices
Duplicated neighbor code means four places for the same bug. The vector array centralizes movement and validation, and diagonal variants become a data change rather than a code change.
2In the spiral walk, what do the two mid-loop guards (top <= bottom, left <= right) prevent?
Index out of range errors
✓ Re-walking a single remaining row or column in the reverse direction on non-square matrices
Infinite loops
Skipping the center element
After the top and right passes consume their bounds, a matrix reduced to one row (or column) would be emitted again backwards without the re-check. Square inputs hide this bug; 1 x n inputs expose it.
3What is the clean in-place decomposition of a 90-degree clockwise rotation?
Reverse each row, then each column
✓ Transpose the matrix, then reverse each row
Swap opposite corners recursively
Reverse the whole matrix, then transpose twice
Transposing maps (i,j) to (j,i); reversing rows then maps column i to column n-1-i - composing to the rotation. Each pass is simple enough to verify independently, unlike the four-way cycle swap.
4In set-matrix-zeroes with O(1) space, why must the first row and column's own status be saved in booleans first?
They are read most often
✓ They are about to be overwritten as the marker storage, destroying the information of whether they originally contained zeros
Because indices start at zero
To keep the passes cache-friendly
Once interior zeros write markers into row 0 and column 0, a zero there could mean 'marker' or 'original'. The two booleans preserve the original meaning, and applying them last avoids premature cascades.
Frequently asked questions
When do grid problems become DFS/BFS problems?
The moment connectivity or distance enters: islands, flood fill, shortest path through a maze, rotting oranges. The grid is just the graph's adjacency; the traversal patterns (visited marking, level-by-level) come from those parent patterns unchanged.
How do I avoid index bugs under interview pressure?
Fix conventions before coding: variables named r and c, grid[r][c] with r vertical, one inBounds helper, directions array. Then trace one small asymmetric example (2x3) by hand. Nearly all grid bugs are convention drift, and conventions are decided in the first thirty seconds.
What is the flatten trick and when is it needed?
Map cell (r, c) to id r * cols + c so a grid can drive 1D structures - union-find over islands being the classic. Reverse with r = id / cols, c = id % cols. It costs nothing and unlocks any index-based structure for grid use.