#70 · Math & Geometry

Set Matrix Zeroes

If an element of an m × n matrix is 0, set its entire row and column to 0, in place (this version also returns the matrix so the result can be checked).

MediumLeetCode

Computing
Depends on
Answer

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Row and column flag arrays

One boolean per row and one per column say whether that row or column must be cleared. Scan once to set the flags, then scan again to write zeros. Recording before writing avoids mistaking new zeros for old ones.

Memory layout

Two arrays of lengths m and n.

Operation	Cost
time	O(m·n)
space	O(m + n)

Flags stored in the matrix itself

The first row and first column of the matrix are reused as the column flags and row flags. Their own original state is saved in one or two booleans, and they are cleared last.

Memory layout

No extra arrays: the matrix doubles as its own storage.

Operation	Cost
space	O(1)

Why it fits

The only information needed per row and column is a single yes/no ("does it contain a zero?"), which fits in one cell.
Because the first row and column are only read for flags before they are overwritten, they can be the flags, provided their own original state is kept separately.
Doing the marking pass completely before the clearing pass is what makes the in-place trick correct.

Why alternatives degrade

Zero rows and columns immediately while scanning:: The zeros you just wrote look like original zeros, so the whole matrix ends up zero.
Storing the coordinates of every zero:: A matrix full of zeros stores m·n pairs: O(m·n) memory.
A sentinel value for "to be zeroed":: It can work if a value outside the range is known, but it needs an extra marking pass and breaks when no such value exists.

Four approaches, from naive to production

1 · beginner

Scan a copy, clear row and column

time O(m·n·(m + n))space O(m·n)

Copy the matrix. Scan the copy; for each zero found, write zeros over its row and column in the real matrix.

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<int>> copy = matrix;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (copy[r][c] != 0) continue;
            for (int k = 0; k < cols; k++) matrix[r][k] = 0;
            for (int k = 0; k < rows; k++) matrix[k][c] = 0;
        }
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] copy = new int[rows][];
    for (int r = 0; r < rows; r++) copy[r] = matrix[r].clone();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (copy[r][c] != 0) continue;
            for (int k = 0; k < cols; k++) matrix[r][k] = 0;
            for (int k = 0; k < rows; k++) matrix[k][c] = 0;
        }
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    copy = [row[:] for row in matrix]
    for r in range(rows):
        for c in range(cols):
            if copy[r][c] != 0: continue
            for k in range(cols): matrix[r][k] = 0
            for k in range(rows): matrix[k][c] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  const copy = matrix.map((row) => [...row]);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (copy[r][c] !== 0) continue;
      for (let k = 0; k < cols; k++) matrix[r][k] = 0;
      for (let k = 0; k < rows; k++) matrix[k][c] = 0;
    }
  }
  return matrix;
}

Flaws & bottlenecks

Extra matrix of the same size.
Clearing a row and column for each zero rewrites the same cells again and again.
Worst case (many zeros) is cubic.

Interviewer cross-questions

Why scan a copy?

Say: Zeros written into the real matrix during the scan would be indistinguishable from the original zeros and would trigger more clearing.

What is the worst case?

Say: A matrix with a zero in every cell: each zero clears a whole row and column, giving O(m·n·(m + n)).

How can the copy be avoided?

Say: Record rows and columns to clear first (flags), then clear them in a second pass.

2 · intermediate

Row flags and column flags

time O(m·n)space O(m + n)

First pass: whenever a cell is zero, set rowZero[r] and colZero[c]. Second pass: set every cell whose row or column is flagged to zero.

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<bool> rowZero(rows, false);
    vector<bool> colZero(cols, false);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                rowZero[r] = true;
                colZero[c] = true;
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
        }
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[] rowZero = new boolean[rows];
    boolean[] colZero = new boolean[cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                rowZero[r] = true;
                colZero[c] = true;
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
        }
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    row_zero = [False] * rows
    col_zero = [False] * cols
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                row_zero[r] = True
                col_zero[c] = True
    for r in range(rows):
        for c in range(cols):
            if row_zero[r] or col_zero[c]: matrix[r][c] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  const rowZero = new Array<boolean>(rows).fill(false);
  const colZero = new Array<boolean>(cols).fill(false);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === 0) {
        rowZero[r] = true;
        colZero[c] = true;
      }
    }
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
    }
  }
  return matrix;
}

Flaws & bottlenecks

Two extra arrays (m + n booleans).
Two full passes over the matrix.
The problem asks for constant extra space, which this does not meet.

Interviewer cross-questions

Why two passes?

Say: The first pass must see only original zeros. Doing all the recording before any writing guarantees that.

Is O(m + n) memory acceptable?

Say: Often yes, and this is the clearest correct answer. If the interviewer asks for O(1), store the flags in the first row and column.

What is the time complexity?

Say: Two scans of m·n cells each: O(m·n).

3 · advanced

First row and column as the flags

time O(m·n)space O(1)

Save whether the first row and first column contain zeros, use cells (r, 0) and (0, c) as the row and column flags for the rest of the matrix, clear the inner cells from those flags, and finally clear the first row and column from the saved booleans.

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColZero = true;
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
    }
    if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColZero = true;
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
    }
    if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = first_col_zero = False
    for c in range(cols):
        if matrix[0][c] == 0: first_row_zero = True
    for r in range(rows):
        if matrix[r][0] == 0: first_col_zero = True
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 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_zero:
        for c in range(cols): matrix[0][c] = 0
    if first_col_zero:
        for r in range(rows): matrix[r][0] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  let firstRowZero = false, firstColZero = false;
  for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRowZero = true;
  for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstColZero = true;
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }
  if (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
  return matrix;
}

Flaws & bottlenecks

The order of the steps is critical: clearing the first row or column too early destroys the flags.
Two special-case booleans and four loops make it error-prone.
It mutates the matrix while it is being read, so it is not thread-safe.

Interviewer cross-questions

Why save the first row and column state before marking?

Say: Marking overwrites cells of the first row and column, so after marking you can no longer tell whether they originally had zeros.

Why are the first row and column cleared last?

Say: The inner cells still need the markers stored there. Only after every inner cell is processed can the first row and column be changed.

How is the answer unaffected by cell (0, 0)?

Say: It belongs to both the first row and the first column; the two saved booleans cover its effect on each of them separately.

4 · expert

Single flag, fill in reverse

time O(m·n)space O(1) (one boolean)

Use one boolean for column 0. Mark with the first row and column as before, but do the final fill from the bottom-right to the top-left, clearing each row's first cell at the end of that row. The first row is then processed last and can serve as both flags and result.

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    bool col0 = false;
    for (int r = 0; r < rows; r++) {
        if (matrix[r][0] == 0) col0 = true;
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 1; c--) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
        if (col0) matrix[r][0] = 0;
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean col0 = false;
    for (int r = 0; r < rows; r++) {
        if (matrix[r][0] == 0) col0 = true;
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 1; c--) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
        if (col0) matrix[r][0] = 0;
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    col0 = False
    for r in range(rows):
        if matrix[r][0] == 0: col0 = True
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    for r in range(rows - 1, -1, -1):
        for c in range(cols - 1, 0, -1):
            if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0
        if col0: matrix[r][0] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  let col0 = false;
  for (let r = 0; r < rows; r++) {
    if (matrix[r][0] === 0) col0 = true;
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }
  for (let r = rows - 1; r >= 0; r--) {
    for (let c = cols - 1; c >= 1; c--) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
    if (col0) matrix[r][0] = 0;
  }
  return matrix;
}

Flaws & bottlenecks

The reverse order is a clever trick whose correctness is hard to see at first.
Easy to break by changing the loop direction or the position of the col0 line.
Mutates the input in place with overlapping roles for cells, so it is hard to debug.

Interviewer cross-questions

Why can the first row act as flags and as its own row at the same time?

Say: Row 0 is filled last. By then every other row has already used the column markers in row 0, and row 0 itself is cleared using its own cell (0, 0) marker for the row, which was set when column 0 or row 0 held a zero.

Why does the fill have to go backwards?

Say: Row 0 and column 0 hold the markers. Going from the bottom-right to the top-left leaves them untouched until every cell that depends on them is finished.

Is the one-boolean version worth the complexity?

Say: It saves a single boolean over the two-flag version. Prefer the clearer one unless the problem statement or a code review explicitly values it.

Synchronized code walkthrough

Showing: Scan a copy, clear row and column — shares the player above; click any step to jump.

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<int>> copy = matrix;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (copy[r][c] != 0) continue;
            for (int k = 0; k < cols; k++) matrix[r][k] = 0;
            for (int k = 0; k < rows; k++) matrix[k][c] = 0;
        }
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    int[][] copy = new int[rows][];
    for (int r = 0; r < rows; r++) copy[r] = matrix[r].clone();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (copy[r][c] != 0) continue;
            for (int k = 0; k < cols; k++) matrix[r][k] = 0;
            for (int k = 0; k < rows; k++) matrix[k][c] = 0;
        }
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    copy = [row[:] for row in matrix]
    for r in range(rows):
        for c in range(cols):
            if copy[r][c] != 0: continue
            for k in range(cols): matrix[r][k] = 0
            for k in range(rows): matrix[k][c] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  const copy = matrix.map((row) => [...row]);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (copy[r][c] !== 0) continue;
      for (let k = 0; k < cols; k++) matrix[r][k] = 0;
      for (let k = 0; k < rows; k++) matrix[k][c] = 0;
    }
  }
  return matrix;
}

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<bool> rowZero(rows, false);
    vector<bool> colZero(cols, false);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                rowZero[r] = true;
                colZero[c] = true;
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
        }
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean[] rowZero = new boolean[rows];
    boolean[] colZero = new boolean[cols];
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (matrix[r][c] == 0) {
                rowZero[r] = true;
                colZero[c] = true;
            }
        }
    }
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
        }
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    row_zero = [False] * rows
    col_zero = [False] * cols
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                row_zero[r] = True
                col_zero[c] = True
    for r in range(rows):
        for c in range(cols):
            if row_zero[r] or col_zero[c]: matrix[r][c] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  const rowZero = new Array<boolean>(rows).fill(false);
  const colZero = new Array<boolean>(cols).fill(false);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === 0) {
        rowZero[r] = true;
        colZero[c] = true;
      }
    }
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rowZero[r] || colZero[c]) matrix[r][c] = 0;
    }
  }
  return matrix;
}

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    bool firstRowZero = false, firstColZero = false;
    for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColZero = true;
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
    }
    if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean firstRowZero = false, firstColZero = false;
    for (int c = 0; c < cols; c++) if (matrix[0][c] == 0) firstRowZero = true;
    for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstColZero = true;
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = 1; r < rows; r++) {
        for (int c = 1; c < cols; c++) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
    }
    if (firstRowZero) for (int c = 0; c < cols; c++) matrix[0][c] = 0;
    if (firstColZero) for (int r = 0; r < rows; r++) matrix[r][0] = 0;
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = first_col_zero = False
    for c in range(cols):
        if matrix[0][c] == 0: first_row_zero = True
    for r in range(rows):
        if matrix[r][0] == 0: first_col_zero = True
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 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_zero:
        for c in range(cols): matrix[0][c] = 0
    if first_col_zero:
        for r in range(rows): matrix[r][0] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  let firstRowZero = false, firstColZero = false;
  for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRowZero = true;
  for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstColZero = true;
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }
  for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }
  if (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
  return matrix;
}

vector<vector<int>> setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    bool col0 = false;
    for (int r = 0; r < rows; r++) {
        if (matrix[r][0] == 0) col0 = true;
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 1; c--) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
        if (col0) matrix[r][0] = 0;
    }
    return matrix;
}

public int[][] setZeroes(int[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    boolean col0 = false;
    for (int r = 0; r < rows; r++) {
        if (matrix[r][0] == 0) col0 = true;
        for (int c = 1; c < cols; c++) {
            if (matrix[r][c] == 0) {
                matrix[r][0] = 0;
                matrix[0][c] = 0;
            }
        }
    }
    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 1; c--) {
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
        }
        if (col0) matrix[r][0] = 0;
    }
    return matrix;
}

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    col0 = False
    for r in range(rows):
        if matrix[r][0] == 0: col0 = True
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    for r in range(rows - 1, -1, -1):
        for c in range(cols - 1, 0, -1):
            if matrix[r][0] == 0 or matrix[0][c] == 0: matrix[r][c] = 0
        if col0: matrix[r][0] = 0
    return matrix

function setZeroes(matrix: number[][]): number[][] {
  const rows = matrix.length, cols = matrix[0].length;
  let col0 = false;
  for (let r = 0; r < rows; r++) {
    if (matrix[r][0] === 0) col0 = true;
    for (let c = 1; c < cols; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }
  for (let r = rows - 1; r >= 0; r--) {
    for (let c = cols - 1; c >= 1; c--) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
    if (col0) matrix[r][0] = 0;
  }
  return matrix;
}