Set matrix zeroes

Medium TimeO(n·m) SpaceO(n + m)

Wherever matrix holds a zero, that zero's whole row and whole column have to be filled with zeros, and the result is written back into the matrix given. Only zeros present in the input trigger a row and column; a zero written along the way does not, or the matrix would empty itself. The matrix need not be square.

Examples

Example 1

Input
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output
[[1,0,1],[0,0,0],[1,0,1]]
One zero, at row 1 column 1, so row 1 and column 1 are cleared and the corners survive.

Example 2

Input
matrix = [[0, 1], [1, 1], [1, 1]]
Output
[[0,0],[0,1],[0,1]]
The zero at row 0 column 0 clears that whole row and the whole left column.

The Code

function setZeroes(matrix) {
  const zeroRows = new Set();
  const zeroCols = new Set();
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < matrix[0].length; c++) {
      if (matrix[r][c] === 0) {
        zeroRows.add(r);
        zeroCols.add(c);
      }
    }
  }
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < matrix[0].length; c++) {
      if (zeroRows.has(r) || zeroCols.has(c)) matrix[r][c] = 0;
    }
  }
  return matrix;
}
setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]);
Done

The first 19 calls, of 33. This one does not fit on a page.

Step through setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]) call by call

More like this

All matrices & grids examples (7) →