Matrix

Matrix problems are about disciplined indexing: row/col boundaries, in-place transforms, and traversal orders. Treat the grid as a coordinate system and design invariants that keep you from stepping outside bounds or corrupting state.

Pattern A: Row/col/box constraints

Use when: you must validate uniqueness across rows, columns, and sub-boxes.

Invariant: each digit appears at most once in each row, column, and box.

Skeleton:

rows[9][9] = false
cols[9][9] = false
boxes[9][9] = false
for r in 0..8:
    for c in 0..8:
        if board[r][c] != '.':
            d = board[r][c] - '1'
            b = (r/3)*3 + (c/3)
            if rows[r][d] or cols[c][d] or boxes[b][d]: return false
            rows[r][d] = cols[c][d] = boxes[b][d] = true

Problems:

• valid-sudoku.

Pattern B: Boundary traversal

Use when: you need spiral or layered traversal.

Invariant: top, bottom, left, right bounds shrink after each edge traversal.

Skeleton:

top=0, bottom=m-1, left=0, right=n-1
while top <= bottom and left <= right:
    traverse top row (left..right), top++
    traverse right col (top..bottom), right--
    if top <= bottom: traverse bottom row (right..left), bottom--
    if left <= right: traverse left col (bottom..top), left++

Problems:

• spiral-matrix.

Pattern C: In-place transforms with markers

Use when: you must update cells based on neighbors without extra space.

Invariant: you can encode old and new state in the same cell.

Skeleton (set zeroes with first row/col markers):

firstRowZero = any zero in row 0
firstColZero = any zero in col 0
for r in 1..m-1:
    for c in 1..n-1:
        if matrix[r][c] == 0:
            matrix[r][0] = 0
            matrix[0][c] = 0
for r in 1..m-1:
    for c in 1..n-1:
        if matrix[r][0] == 0 or matrix[0][c] == 0:
            matrix[r][c] = 0
if firstRowZero: zero row 0
if firstColZero: zero col 0

Skeleton (game of life encoding):

// bit0 = old, bit1 = new
for each cell:
    liveNeighbors = count cells with (value & 1) == 1
    if old == 1 and (liveNeighbors == 2 or 3): value |= 2
    if old == 0 and liveNeighbors == 3: value |= 2
for each cell: value >>= 1

Problems:

• set-matrix-zeroes.
• game-of-life.

Pattern D: In-place rotation by transpose + reverse

Use when: rotating an N x N matrix by 90 degrees.

Invariant: transpose swaps (r,c) with (c,r); reversing rows completes rotation.

Skeleton:

for r in 0..n-1:
    for c in r+1..n-1:
        swap(matrix[r][c], matrix[c][r])
for r in 0..n-1:
    reverse(matrix[r])

Problems:

• rotate-image.

Pattern E: Diagonal traversal by sum parity

Use when: you traverse diagonals in zigzag order.

Invariant: all cells with equal (r+c) are on the same diagonal.

Skeleton:

for d in 0..m+n-2:
    if d even: walk up-right along diagonal
    else: walk down-left along diagonal

Problems:

• diagonal-traverse.

When to use Matrix techniques (checklist)

• You can define the traversal order explicitly.
• The update depends on local neighbors or row/col constraints.
• In-place updates are required or desirable.

Common failures (checklist)

• Off-by-one errors when shrinking bounds.
• Overwriting state before it is read (missing encoding or markers).
• Mixing row/col indices or box indexing formulas.
• Forgetting to handle single-row or single-column cases.

Problem mapping

• valid-sudoku: row/col/box constraint sets.
• spiral-matrix: boundary traversal.
• rotate-image: transpose + reverse.
• set-matrix-zeroes: first row/col markers.
• game-of-life: in-place state encoding.
• diagonal-traverse: diagonal sum parity.