Zero Out Rows and Columns Containing a Zero

medium matrix in-place

Problem

If any cell of an m × n matrix is 0, set its entire row and column to 0. To do it with O(1) extra space, repurpose the first row and first column as flags: scan the matrix and stamp matrix[r][0] or matrix[0][c] whenever the inner cell is 0. Remember separately whether row 0 or column 0 themselves contain a zero, then sweep the body of the matrix using those flags, and zero the first row/column last.

Input[[1,1,1],[1,0,1],[1,1,1]]

Output[[1,0,1],[0,0,0],[1,0,1]]

The middle 0 zeroes its row and column.

matrix (rows separated by ';', values by ',')

def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][c] == 0 for c in range(n))
    first_col = any(matrix[r][0] == 0 for r in range(m))
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row:
        for c in range(n): matrix[0][c] = 0
    if first_col:
        for r in range(m): matrix[r][0] = 0

function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let firstRow = false, firstCol = false;
  for (let c = 0; c < n; c++) if (matrix[0][c] === 0) firstRow = true;
  for (let r = 0; r < m; r++) if (matrix[r][0] === 0) firstCol = true;
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      if (matrix[r][c] === 0) {
        matrix[r][0] = 0;
        matrix[0][c] = 0;
      }
    }
  }
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      if (matrix[r][0] === 0 || matrix[0][c] === 0) matrix[r][c] = 0;
    }
  }
  if (firstRow) for (let c = 0; c < n; c++) matrix[0][c] = 0;
  if (firstCol) for (let r = 0; r < m; r++) matrix[r][0] = 0;
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for (int c = 0; c < n; c++) if (matrix[0][c] == 0) firstRow = true;
        for (int r = 0; r < m; r++) if (matrix[r][0] == 0) firstCol = true;
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
            }
        }
        if (firstRow) for (int c = 0; c < n; c++) matrix[0][c] = 0;
        if (firstCol) for (int r = 0; r < m; r++) matrix[r][0] = 0;
    }
}

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    bool firstRow = false, firstCol = false;
    for (int c = 0; c < n; ++c) if (matrix[0][c] == 0) firstRow = true;
    for (int r = 0; r < m; ++r) if (matrix[r][0] == 0) firstCol = true;
    for (int r = 1; r < m; ++r)
        for (int c = 1; c < n; ++c)
            if (matrix[r][c] == 0) { matrix[r][0] = 0; matrix[0][c] = 0; }
    for (int r = 1; r < m; ++r)
        for (int c = 1; c < n; ++c)
            if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;
    if (firstRow) for (int c = 0; c < n; ++c) matrix[0][c] = 0;
    if (firstCol) for (int r = 0; r < m; ++r) matrix[r][0] = 0;
}

Time: O(m · n) Space: O(1)