Set Matrix Zero

Mark as Completed

Lesson

Given a 2D matrix, if an element is 0, set its entire row and column to 0. Write a function to do this in place, meaning you cannot create a new array. Explain your approach and provide the Big O complexity of the solution.

Solution Walkthrough

Solution Code

function setZeros(matrix) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  let firstRowHasZero = false;
  let firstColHasZero = false;

  // check if first row has a zero
  for (let col = 0; col < numCols; col++) {
    if (matrix[0][col] === 0) {
      firstRowHasZero = true;
      break;
    }
  }

  // check if first column has a zero
  for (let row = 0; row < numRows; row++) {
    if (matrix[row][0] === 0) {
      firstColHasZero = true;
      break;
    }
  }

  // check for zeros in the rest of the matrix
  for (let row = 1; row < numRows; row++) {
    for (let col = 1; col < numCols; col++) {
      if (matrix[row][col] === 0) {
        matrix[row][0] = 0;
        matrix[0][col] = 0;
      }
    }
  }

  // set zeros based on first row and column
  for (let col = 1; col < numCols; col++) {
    if (matrix[0][col] === 0) {
      for (let row = 1; row < numRows; row++) {
        matrix[row][col] = 0;
      }
    }
  }
  for (let row = 1; row < numRows; row++) {
    if (matrix[row][0] === 0) {
      for (let col = 1; col < numCols; col++) {
        matrix[row][col] = 0;
      }
    }
  }

  // set zeros for first row and column
  if (firstRowHasZero) {
    for (let col = 0; col < numCols; col++) {
      matrix[0][col] = 0;
    }
  }
  if (firstColHasZero) {
    for (let row = 0; row < numRows; row++) {
      matrix[row][0] = 0;
    }
  }
}

Explanation

The solution is divided into three parts. In the first part, we iterate through the first row and first column to check if they have any zeros. This is because if the first row or first column has a zero, then we need to set the entire row or column to zero later. We use two boolean variables, firstRowHasZero
and firstColHasZero
, to keep track of whether the first row and first column have zeros or not.In the second part, we iterate through the rest of the matrix (excluding the first row and first column) to find the zeros. If a zero is found at (i, j)
, we set the value of matrix[0][j]
and matrix[i][0]
to zero. This is because we will set the entire row and column to zero later based on the values in the first row and first column.In the third part, we set the zeros for each row and column based on the values in the first row and first column. We also set the zeros for the first row and first column if firstRowHasZero
or firstColHasZero
is true
, respectively.

The solution modifies the input matrix in place without creating a new array. It meets the requirement of the problem by manipulating the input instead of creating a new array.

Big O Complexity Analysis: The time complexity of this solution is O(mn), where m is the number of rows and n is the number of columns. We iterate through the entire matrix three times. The space complexity of this solution is O(1), as we are modifying the input matrix in place without creating a new array. We only use constant extra space for the boolean variables.

Previous Lesson Next Lesson