Set Matrix Zeroes

medium matrix in-place

Problem

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

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;
}

Explanation

Whenever a cell is 0, its whole row and column must become 0. The naive fix needs extra arrays to remember which rows and columns to zero, but the clever trick is to reuse the matrix's own first row and first column as the notepad, giving constant extra space.

Because the first row and column will be used as flags, we first record separately whether they themselves originally contained a zero, in firstRow and firstCol. Then we scan the inner cells: every time we see matrix[r][c] == 0, we mark it by setting matrix[r][0] = 0 and matrix[0][c] = 0.

Next we make a second pass over the inner cells and zero any cell whose row flag matrix[r][0] or column flag matrix[0][c] is 0. Finally, using the two booleans we saved earlier, we zero the first row and/or first column if they originally needed it. Doing this last avoids prematurely wiping our own flags.

Example: [[1,1,1],[1,0,1],[1,1,1]]. The single 0 at the center flags row 1 and column 1, and the result is [[1,0,1],[0,0,0],[1,0,1]].

We sweep the grid a fixed number of times, so it is linear in the number of cells and uses only O(1) extra memory.

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