set-matrix-zeroes.ts

/**
 * 73. Set Matrix Zeroes  (Medium)
 * Link: https://leetcode.com/problems/set-matrix-zeroes/
 *
 * If an element in an m x n matrix is 0, set its entire row and column to 0, in
 * place.
 *
 * Example:
 *   Input:  [[1,1,1],[1,0,1],[1,1,1]]
 *   Output: [[1,0,1],[0,0,0],[1,0,1]]
 *
 * Approach:
 *   Use the first row and first column as marker storage instead of extra
 *   O(m+n) arrays. First record whether row 0 / col 0 themselves must be zeroed.
 *   Then for each inner zero, mark its row's and column's header. Finally apply
 *   the markers, and zero the first row/column last so markers survive.
 *
 * Time:  O(m * n)
 * Space: O(1)
 */
export function setZeroes(matrix: number[][]): void {
  const rows = matrix.length;
  const cols = matrix[0].length;
  let firstRowZero = false;
  let firstColZero = false;

  for (let c = 0; c < cols; c++) if (matrix[0][c] === 0) firstRowZero = true;
  for (let r = 0; r < rows; r++) if (matrix[r][0] === 0) firstColZero = 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 (firstRowZero) for (let c = 0; c < cols; c++) matrix[0][c] = 0;
  if (firstColZero) for (let r = 0; r < rows; r++) matrix[r][0] = 0;
}