Problem Overview & Intuition

Instead of allocating additional memory for row and column markers, use matrix[i][0] and matrix[0][j] to record zeroes. Use a single boolean flag for the first column.

Step-by-Step Approach

1. Scan the matrix and record zero occurrences in row 0 and column 0.
2. Use col0 to record if column 0 contains any zeroes.
3. Iterate backwards from bottom-right to update cells based on row and column markers.
4. Return matrix.

Optimal Implementation (JavaScript)

function setZeroes(matrix) {
  let col0 = 1;
  const m = matrix.length, n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) col0 = 0;
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] = 0;
        matrix[0][j] = 0;
      }
    }
  }
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 1; j--) {
      if (matrix[i][0] === 0 || matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
    if (col0 === 0) matrix[i][0] = 0;
  }
  return matrix;
}

Complexity Analysis