Set Matrix Zeroes

Examples

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

The single 0 sits at row 1, column 1, so all of row 1 and all of column 1 become 0.

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Two zeros exist - at (0,0) and (0,3) - so rows 0 gets fully zeroed, and columns 0 and 3 get zeroed everywhere.

Constraints

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 200

• -2^31 <= matrix[i][j] <= 2^31 - 1

Approach

The key trap in this problem is that zeroing cells out as you scan would create brand-new zeros that then incorrectly trigger even more rows and columns to be cleared. So any approach needs to first record which rows and columns must be zeroed, and only apply that in a separate pass.

A straightforward way to record that is with a set of row indexes and a set of column indexes, built in one scan of the grid. A second scan then zeroes out any cell whose row or column appears in those sets.

To bring the extra memory down to a constant amount, reuse the grid's own first row and first column as the "which rows/columns need zeroing" markers, instead of separate sets. The only extra bookkeeping needed is remembering, with two single booleans, whether the first row and first column themselves originally contained a zero - since they're about to be reused as markers.

Solutions

Brute Force - Track Rows/Columns With Sets

Scan the whole grid once, recording in a set of rows and a set of columns every row and column that contains at least one 0. Then scan again, zeroing out any cell whose row or column is in one of those sets.

function setZeroes(matrix) {
  const rows = new Set();
  const cols = new Set();
  const m = matrix.length, n = matrix[0].length;

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (matrix[r][c] === 0) {
        rows.add(r);
        cols.add(c);
      }
    }
  }

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (rows.has(r) || cols.has(c)) {
        matrix[r][c] = 0;
      }
    }
  }
}

Time: O(m · n) · Space: O(m + n), for the row and column sets

Optimal - Use the First Row and Column as Markers

Instead of separate sets, use matrix[r][0] and matrix[0][c] themselves to mark 'row r needs zeroing' and 'column c needs zeroing'. Since that overwrites the first row/column's own values, first remember (in two booleans) whether the first row and first column originally contained a zero, then apply their markers last.

function setZeroes(matrix) {
  const m = matrix.length, n = matrix[0].length;
  let firstRowHasZero = false;
  let firstColHasZero = false;

  for (let c = 0; c < n; c++) if (matrix[0][c] === 0) firstRowHasZero = true;
  for (let r = 0; r < m; r++) if (matrix[r][0] === 0) firstColHasZero = true;

  // Use row 0 and column 0 as marker space for every other row/column
  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 (firstRowHasZero) for (let c = 0; c < n; c++) matrix[0][c] = 0;
  if (firstColHasZero) for (let r = 0; r < m; r++) matrix[r][0] = 0;
}

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