Set Matrix Zeroes

If a cell is zero, set its full row and column to zero. Change the matrix in place.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Set Matrix Zeroes: Preserve first-row and first-column facts, store interior zero instructions in those borders, then apply markers before restoring the borders.

Input and goalIf a cell is zero, set its full row and column to zero. Change the matrix in place.

Inspect the original bordersFor [[1,0,3],[4,5,6],[7,8,0]], the first row contains 0 but the first column does not.

10scan3456780

coordinatesrow,columnfirstRowZerotruefirstColZerofalseactionsave border facts before overwriting markers

Recognize it

Use border markers when entire rows and columns must change from discovered cells, but the required extra space must remain constant.

Keep true

After the marker pass, matrix[r][0]=0 means interior row r must be zeroed and matrix[0][c]=0 means interior column c must be zeroed; saved booleans independently preserve the original first-border obligations.

Reuse it

When output overwrites input, identify safe in-place metadata cells and separately save any original facts those cells represented before reusing them.

Pattern: Use the first row and first column as marker storage.

Simple idea: Mark row r at matrix[r][0] and column c at matrix[0][c]. Save two booleans because the first row and first column also contain real input.

def _mark_zero_rows_and_cols(matrix: list[list[int]]) -> None:
   for row in range(1, len(matrix)):
      for col in range(1, len(matrix[0])):
         if matrix[row][col] == 0:
            matrix[row][0] = matrix[0][col] = 0


def _fill_marked_zeroes(matrix: list[list[int]]) -> None:
   for row in range(1, len(matrix)):
      for col in range(1, len(matrix[0])):
         if matrix[row][0] == 0 or matrix[0][col] == 0:
            matrix[row][col] = 0


def set_zeroes(matrix: list[list[int]]) -> None:
   if not matrix or not matrix[0]:
      return

   first_row_zero = 0 in matrix[0]
   first_col_zero = any(row[0] == 0 for row in matrix)
   _mark_zero_rows_and_cols(matrix)
   _fill_marked_zeroes(matrix)

   if first_row_zero:
      matrix[0] = [0] * len(matrix[0])
   if first_col_zero:
      for row in matrix:
         row[0] = 0

Cost: $O(rows\times cols)$ time and $O(1)$ extra space.