125. Set Matrix Zeroes

Why this mechanism works

The first row and first column can store markers for the rest of the matrix, but their original zero status must be saved separately. Discover all markers before applying them. This separates observation of original state from propagation of new state.

State and boundaries

first_row and first_col remember original boundary-zero flags. Interior zeros mark matrix[r][0] and matrix[0][c].

Protocol

1. Save the first row and column flags.
2. Mark rows and columns from original interior zeros.
3. Zero interior cells indicated by markers.
4. Apply the saved first-row and first-column flags last.

Visualization

original center zero
mark its row at first column
mark its column at first row
apply markers only after discovery is complete

Python implementation

def set_zeroes(matrix):
    if not matrix or not matrix[0]:
        return matrix
    rows, cols = len(matrix), len(matrix[0])
    first_row = any(value == 0 for value in matrix[0])
    first_col = any(row[0] == 0 for row in matrix)
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row:
        for c in range(cols):
            matrix[0][c] = 0
    if first_col:
        for r in range(rows):
            matrix[r][0] = 0
    return matrix

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 set_zeroes: if not matrix or not matrix[0]:
matrix=[[1, 1, 1], [1, 0, 1], [1, 1, 1]]

L4 set_zeroes: rows, cols = len(matrix), len(matrix[0])
matrix=[[1, 1, 1], [1, 0, 1], [1, 1, 1]]; rows=3; cols=3

L5 <genexpr>: first_row = any(value == 0 for value in matrix[0])
.0=list_iterator; value=1

L5 <genexpr>: first_row = any(value == 0 for value in matrix[0])
.0=list_iterator; value=1

L5 <genexpr>: first_row = any(value == 0 for value in matrix[0])
.0=list_iterator; value=1

L5 <genexpr>: first_row = any(value == 0 for value in matrix[0])
.0=list_iterator; value=1

L5 set_zeroes: first_row = any(value == 0 for value in matrix[0])
matrix=[[1, 1, 1], [1, 0, 1], [1, 1, 1]]; rows=3; cols=3; first_row=False

L6 <genexpr>: first_col = any(row[0] == 0 for row in matrix)
.0=list_iterator; row=[1, 1, 1]

... 15 intermediate state changes omitted ...

L11 set_zeroes: for r in range(1, rows):
matrix=[[1, 0, 1], [0, 0, 0], [1, 1, 1]]; rows=3; cols=3; first_row=False; first_col=False; r=2; c=2

L12 set_zeroes: for c in range(1, cols):
matrix=[[1, 0, 1], [0, 0, 0], [1, 1, 1]]; rows=3; cols=3; first_row=False; first_col=False; r=2; c=1

L14 set_zeroes: matrix[r][c] = 0
matrix=[[1, 0, 1], [0, 0, 0], [1, 0, 1]]; rows=3; cols=3; first_row=False; first_col=False; r=2; c=1

L12 set_zeroes: for c in range(1, cols):
matrix=[[1, 0, 1], [0, 0, 0], [1, 0, 1]]; rows=3; cols=3; first_row=False; first_col=False; r=2; c=2

L2 set_zeroes: if not matrix or not matrix[0]:
matrix=[[0, 1], [2, 3]]

L4 set_zeroes: rows, cols = len(matrix), len(matrix[0])
matrix=[[0, 1], [2, 3]]; rows=2; cols=2

L5 <genexpr>: first_row = any(value == 0 for value in matrix[0])
.0=list_iterator; value=0

L5 set_zeroes: first_row = any(value == 0 for value in matrix[0])
matrix=[[0, 1], [2, 3]]; rows=2; cols=2; first_row=True

L6 <genexpr>: first_col = any(row[0] == 0 for row in matrix)
.0=list_iterator; row=[0, 1]

L6 set_zeroes: first_col = any(row[0] == 0 for row in matrix)
matrix=[[0, 1], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True

L7 set_zeroes: for r in range(1, rows):
matrix=[[0, 1], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=1

L8 set_zeroes: for c in range(1, cols):
matrix=[[0, 1], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=1; c=1

... 2 intermediate state changes omitted ...

L17 set_zeroes: matrix[0][c] = 0
matrix=[[0, 0], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=1; c=1

L19 set_zeroes: for r in range(rows):
matrix=[[0, 0], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=0; c=1

L19 set_zeroes: for r in range(rows):
matrix=[[0, 0], [2, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=1; c=1

L20 set_zeroes: matrix[r][0] = 0
matrix=[[0, 0], [0, 3]]; rows=2; cols=2; first_row=True; first_col=True; r=1; c=1

Why the solution is correct

Marker discovery reads only original interior cells and writes only boundary cells, so it cannot create new interior evidence. The markers therefore identify exactly the required rows and columns. Applying them after discovery, then restoring boundary behavior from saved flags, implements precisely the original-zero rule.

Time and space

O(rows*cols) time and O(1) auxiliary space.

Common mistakes

Zeroing immediately while scanning causes cascades from newly written zeros. Using matrix[0][0] alone cannot independently remember both boundary flags.

Reasoning card

Transfer exercise

Build a simpler O(rows+cols)-space reference and use it as an independent oracle for the marker implementation.