Set Matrix Zeroes

Given an m x n matrix, if any cell is 0, set its entire row and column to 0. Do it in-place with O(1) extra space.

Why this is worth learning

The first row and column become metadata storage. Their original zero status must be saved before the algorithm writes its own markers.

Before coding: one-minute experiment

Why can matrix[0][0] alone not describe both the original first-row and first-column zero conditions?

Function signature

func SetZeroes(matrix [][]int)

Inputs / outputs

• matrix: matrix to modify in-place.
• Return: nothing; modify matrix.

Example

matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
After:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Constraints

• 0 <= m, n <= 1000

Core idea (near-solution)

Use the first row and first column as marker storage:

• If matrix[i][j] is zero, mark matrix[i][0] = 0 and matrix[0][j] = 0.
• Use two extra flags to remember whether the first row and first column themselves should be zeroed.

Invariant: after the marking pass, markers correctly identify which rows/cols need zeroing.

Algorithm (step-by-step)

1. Return immediately if there are no rows or no columns. Otherwise scan the first row and first column to set row0Zero and col0Zero flags.
2. For each cell (i,j) starting from (1,1):
   • If matrix[i][j] == 0, set matrix[i][0] = 0 and matrix[0][j] = 0.
3. For each cell (i,j) starting from (1,1):
   • If matrix[i][0] == 0 or matrix[0][j] == 0, set matrix[i][j] = 0.
4. If row0Zero, zero the first row; if col0Zero, zero the first column.

Correctness sketch

First record whether the original first row or first column contains zero. Scanning only interior cells then sets row and column markers exactly for original interior zeros; marker writes cannot affect an unscanned interior value. In the second interior pass, a marker in either axis is equivalent to an original zero somewhere in that cell's row or column, so zero exactly the required cells. The first-row and first-column flags handle their independent original conditions after their marker role is finished. Deferring these final writes avoids erasing metadata prematurely. Every required row and column is covered, and a nonzero cell outside all marked axes is preserved.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
After:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Walk:
- zero at (1,1) => mark row 1 and col 1
- zero row 1 -> [0,0,0] in middle
- zero col 1 -> final [[1,0,1],[0,0,0],[1,0,1]]

Pitfalls to avoid

• Overwriting markers too early.
• Forgetting to handle the first row/column separately.

Debugging lens

Test [[1,0],[1,1]] and [[1,1],[0,1]] separately. Zeroing an entire row during discovery creates artificial zeros that would incorrectly propagate into unrelated columns.

Complexity

• Time: O(m*n)
• Extra space: O(1)

Implementation notes (Go)

• Use the first row/col as markers and track separate flags.
• Zero the first row/col at the end based on flags.

Contract precision

Rectangular empty and zero-column inputs are supported. Row and column decisions are based on the original matrix, not zeros introduced by this update.

Reconstruction checkpoint

Why can matrix[0][0] alone not describe both the original first-row and first-column zero conditions?

Return to Matrix · Module quiz