medium

Set Matrix Zeroes

Zero out the row and column of every zero in a matrix, in place.

1. Define the problem

Set Matrix Zeroes

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0. You must do it in place — using the first row and first column of the matrix itself as marker flags avoids needing extra memory for the whole matrix.

Constraints

  • m == matrix.length
  • n == matrix0.length
  • 1 ≤ m, n ≤ 200
  • -231 ≤ matrixi[j] ≤ 231 - 1

Example

Inputmatrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output[[1, 0, 1], [0, 0, 0], [1, 0, 1]]

Explanation The single 0 at (1, 1) zeroes out all of row 1 and all of column 1.

2. Know the words first

In plain terms

Marker flags
A cell reused to record a fact ("this row/column needs zeroing") instead of allocating a brand-new array to hold that same information.
3. Visualize the solution

Mark rows and columns to zero, then apply the marks

Mark rows and columns to zero, then apply the marks
Statusflags

Check the first row and first column for zeros before reusing them as markers: neither has one.

What happens in this step

firstRowHasZero = false
firstColHasZero = false

Neither the first row [1,1,1] nor the first column [1,1,1] contains a 0, so both flags stay false.
Step 1 of 5

Steps to visualize

  1. First check whether the first row or first column itself already contains a zero, and remember that separately — they're about to be reused as markers.
  2. Scan the rest of the matrix: whenever a cell is 0, mark its row in the first column and its column in the first row.
  3. Scan again: zero out any cell whose row-marker or column-marker is set.
  4. Finally, if the first row or first column originally had a zero, zero the whole row or column now.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Mark rows and columns to zero, then apply the marks
Statusflags

Check the first row and first column for zeros before reusing them as markers: neither has one.

What happens in this step

firstRowHasZero = false
firstColHasZero = false

Neither the first row [1,1,1] nor the first column [1,1,1] contains a 0, so both flags stay false.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function setZeroes(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowHasZero = false;
  let firstColHasZero = false;

  for (let col = 0; col < cols; col++) {
    if (matrix[0][col] === 0) {
      firstRowHasZero = true;
    }
  }

  for (let row = 0; row < rows; row++) {
    if (matrix[row][0] === 0) {
      firstColHasZero = true;
    }
  }

  for (let row = 1; row < rows; row++) {
    for (let col = 1; col < cols; col++) {
      if (matrix[row][col] === 0) {
        matrix[row][0] = 0;
        matrix[0][col] = 0;
      }
    }
  }

  for (let row = 1; row < rows; row++) {
    for (let col = 1; col < cols; col++) {
      if (matrix[row][0] === 0 || matrix[0][col] === 0) {
        matrix[row][col] = 0;
      }
    }
  }

  if (firstRowHasZero) {
    for (let col = 0; col < cols; col++) {
      matrix[0][col] = 0;
    }
  }

  if (firstColHasZero) {
    for (let row = 0; row < rows; row++) {
      matrix[row][0] = 0;
    }
  }

  return matrix;
}
Time
O(m * n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
matrix = [[1, 1, 1], [1, 0, 1], [1, 1, 1]][[1, 0, 1], [0, 0, 0], [1, 0, 1]]example from the docstring
matrix = [[1]][[1]]smallest valid input with no zero present
matrix = [[0]][[0]]smallest valid input that is already zero
matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8]][[0, 0, 0], [0, 4, 5], [0, 7, 8]]the zero sits in both the first row and first column, the markers themselves
matrix = [[0, 0], [0, 0]][[0, 0], [0, 0]]a matrix that is already all zeroes
matrix = [[1, 2], [3, 4]][[1, 2], [3, 4]]no zero anywhere, so nothing changes

Keep reading