Matrix

Reader guide and study workflow · Complete course map

A board [[1,2,3],[4,0,6]] must erase every row and column containing an original zero. Imagine scanning left to right and immediately erasing each row you encounter: what happens when the scan reaches the new zero written at (1,2)?

Separate facts from the writes they cause

Immediate erasure treats that new zero as another cause, incorrectly erasing column 2. The required answer is [[1,0,3],[0,0,0]]; entries 1 and 3 must survive. A copied board gives a simple correct model: read original cells from the copy and write consequences to the destination.

Can the copy be summarized? The only facts needed for this problem are which rows and which columns originally contained zeros. Two boolean arrays suffice. If constant extra space is required, store those flags in the first row and column. Their own original conditions need separate flags, because those cells now serve as metadata. Finish discovery before applying markers to the interior, and finalize the marker axes last.

This derives the storage scheme from the information needed by future reads. Game of Life needs more detailed original information—each neighboring cell's old state—so row/column summaries are insufficient; two bits per cell preserve both times. Rotation is different again: it permutes values, so a coordinate map is the useful starting model.

For each grid problem, first decide whether you are validating a state, enumerating positions, permuting values, or simulating a new time step. The workshop shows how that decision determines which reads and writes may safely share storage.

Prerequisites and readiness

Know rectangular versus square grids, row-major access, exclusive slices, and basic bit operations. Be able to state which reads require original values and which cells are safe to overwrite.

Reasoning workshop: geometry and time are separate contracts

Derive a coordinate map first

For clockwise rotation, write where one original value must go: (r,c) → (c,n-1-r). Transposition supplies the first exchange of coordinates, and row reversal supplies the second reflection. In a numbered 2-by-2 matrix [[1,2],[3,4]], transpose gives [[1,3],[2,4]], then row reversal gives [[3,1],[4,2]]. Applying row reversal before transposition would rotate in the other direction. The order of composed transformations matters.

Spiral and diagonal traversals do not mutate coordinates into new positions; they enumerate existing cells. Give each cell a distinct ID so a missing or repeated visit is visible. For [[1,2,3],[4,5,6]], spiral order is 1,2,3,6,5,4, while diagonal order is 1,2,4,5,3,6. Neither traversal can be inferred from the other by simply reversing the output.

Shrinking boundaries are a representation of the remainder

The spiral remainder is a rectangle. After emitting its top row, that row no longer belongs to the rectangle. After emitting the right column, the top-right corner is already excluded by the updated top bound. The remaining bottom and left sweeps need extra guards because a thin rectangle may have disappeared during the first two sweeps. Always test 1-by-N and N-by-1 before assuming a square example proves boundary correctness.

A diagonal instead keeps r+c=d constant. For even d, decreasing r and increasing c walks upward-right; for odd d the direction reverses. Enumerating each coordinate sum exactly once partitions the whole matrix into disjoint diagonals and gives a clean no-duplicates proof.

Metadata must not masquerade as original data

Set Matrix Zeroes needs the zero locations of the original board. Writing zeros immediately across a discovered row creates new zeros that a later scan could misinterpret as original causes. Use the first row and column as markers, but save their own original conditions first. The intersection cell (0,0) cannot encode two independent yes/no flags on its own. Only after all interior decisions are made can the first axes be finalized.

Game of Life solves a related information problem with two bits per cell. Value 3 means old live and next live; value 2 means old dead and next live. Neighbor reads must mask the old bit. The horizontal blinker 000 / 111 / 000 becomes 010 / 010 / 010; an immediate overwrite implementation often destroys this synchronous behavior. A second pass shifts the new bit into place only after every next state has been decided.

Validation is not solving

Sudoku checks three uniqueness families: row, column, and 3-by-3 box. Two equal digits at (0,0) and (1,1) violate only the box rule. A valid partial board need not have a completion; proving solvability is a different search problem. The input is always 9-by-9, so both work and mask storage are constant for this interface.

Testing beyond pretty squares

Use a copied-board oracle for zero propagation and life updates, a direct coordinate-scatter oracle for rotation, and a visited-cell direction simulator for spiral order. These oracles should differ structurally from the optimized references. Metamorphic checks such as four rotations restoring the original are useful supplements, but not complete specifications: doing nothing also passes that identity. Rectangular empty inputs are supported where stated; ragged rows are not a hidden extension of the contract.

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

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: updates need original row/column facts or original neighbor states, but a full second grid is unnecessary.

Invariant: the storage scheme preserves every original fact until its last required read. Zero markers record affected axes; two-bit life encoding stores two generations.

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

if m == 0 or n == 0: return
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:
    old = value & 1
    liveNeighbors = count in-bounds neighbors whose (value & 1) == 1
    if liveNeighbors == 3 or (old == 1 and liveNeighbors == 2): 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.

Reconstruction lab and answer key

Close the worked examples before attempting these new cases. Rebuild the state and justify the update, then compare with the model answer.

Valid Sudoku

Place equal digits at (2,2) and (3,3), with every other cell empty. Should a validator reject them just because the cells touch diagonally? Derive both box indices.

Model answer

No. Their box indices are 0 and 4, and both rows and columns differ. Diagonal adjacency imposes no Sudoku rule. The box formula groups coordinates by integer division, not geometric proximity.

Spiral Matrix

Rebuild the boundary guards for a three-row, one-column matrix. Which sweep consumes which cells, and which later sweeps must do no work?

Model answer

The top sweep emits row 0, then top becomes 1. The right sweep emits rows 1 and 2, then right becomes -1. The bottom sweep has an empty column range; the left sweep is skipped because left>right. Every cell is emitted once.

Rotate Image

Without running code, derive the coordinate transformation produced by reversing each original row first and then transposing. Which way does it rotate?

Model answer

Row reversal sends (r,c) to (r,n-1-c). Transposition then gives (n-1-c,r), a counterclockwise rotation. The two operations are the same but their order changes the composition.

Set Matrix Zeroes

For [[1,2,0],[4,5,6]], give the two original-axis flags and explain why applying the first-row flag before finishing the interior would be wrong.

Model answer

row0Zero=true and col0Zero=false. The original zero marks column 2. Final output is [[0,0,0],[4,5,0]]. Clearing row 0 early would turn its other entries into false column markers and erase 4 and 5.

Game of Life

On a board containing one live cell, what value does that cell hold after the encoding pass and after the final shift? Explain why these differ.

Model answer

It has no live neighbors, so its next state is dead. Its encoded value remains 1 (binary 01: old live, next dead); after shifting it becomes 0. A dying cell must still contribute one to old-state neighbor counts until all decisions finish.

Diagonal Traverse

For a matrix with four rows and two columns, derive the starting coordinate and direction for diagonals d=2 and d=3.

Model answer

For even d=2, r=min(2,3)=2 and c=0, so walk (2,0),(1,1) upward-right. For odd d=3, c=min(3,1)=1 and r=2, so walk (2,1),(3,0) downward-left. Rows and columns use different bounds.

Problems in this module

• Valid Sudoku
• Spiral Matrix
• Rotate Image
• Set Matrix Zeroes
• Game of Life
• Diagonal Traverse

Interactive checkpoint

Open the Matrix quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable