Frontend Beauty
ESC

Type to search the knowledge base.

Set Matrix Zeroes

If a cell is 0, zero its row and column — mark in-place with first row/col flags, O(1) extra space.

intermediate3 min read
  • dsa
  • arrays
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Given an m × n integer 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]]

Brute force

Copy matrix; whenever original is 0, zero row/col in copy. O(mn) space.

Or: first pass record all zero positions, second pass zero rows/cols. O(m+n) or O(k) space.

function setZeroesExtra(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const zr = new Set<number>();
  const zc = new Set<number>();
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (matrix[r][c] === 0) {
        zr.add(r);
        zc.add(c);
      }
    }
  }
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (zr.has(r) || zc.has(c)) matrix[r][c] = 0;
    }
  }
}
Time O(m · n)
Space O(m + n)

Optimal: use first row and first column as markers

  1. Track whether first row / first col originally contain a zero.
  2. For r≥1, c≥1, if matrix[r][c]==0, set matrix[r][0]=0 and matrix[0][c]=0.
  3. Zero cells based on markers.
  4. Finally zero first row/col using the flags.
function setZeroes(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRow = false;
  let firstCol = false;

  for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRow = true;
  for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstCol = true;

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

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

  if (firstRow) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  if (firstCol) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
}
Time O(m · n)
Space O(1)

Edge cases

  • Zero only in first row/col
  • Entire matrix becomes zero
  • No zeros — unchanged
  • Single row or single column

Common bugs

  • Zeroing first row early and destroying markers
  • Forgetting separate firstRow/firstCol flags
  • Using a sentinel like null in a number matrix without care

Interview delivery

  1. O(m+n) sets is acceptable mid-level.
  2. Push O(1): marker row/col.
  3. Order of zeroing matters.
  4. Complexity O(mn)/O(1).

Further reading