Set Matrix Zeroes: Efficient In-Place Modification

The "Set Matrix Zeroes" problem involves modifying a matrix in-place, setting entire rows and columns to zero where any element in them is zero.

Problem Statement

Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example

• Input: Matrix [ [1,1,1], [1,0,1], [1,1,1] ]

• Output: [ [1,0,1], [0,0,0], [1,0,1] ]

Solution Approach - Space Optimized

function setZeroes(matrix: number[][]): void {
  if (matrix.length === 0 || matrix[0].length === 0) return;

  let isCol = false;
  const R = matrix.length;
  const C = matrix[0].length;

  for (let i = 0; i < R; i++) {
      if (matrix[i][0] === 0) isCol = true;
      for (let j = 1; j < C; j++) {
          if (matrix[i][j] === 0) {
              matrix[i][0] = 0;
              matrix[0][j] = 0;
          }
      }
  }

  for (let i = 1; i < R; i++) {
      for (let j = 1; j < C; j++) {
          if (matrix[i][0] === 0 || matrix[0][j] === 0) matrix[i][j] = 0;
      }
  }

  if (matrix[0][0] === 0) {
      for (let j = 0; j < C; j++) matrix[0][j] = 0;
  }

  if (isCol) {
      for (let i = 0; i < R; i++) matrix[i][0] = 0;
  }
}

Breaking Down the Solution

• Mark Zeroes: Iterate through the matrix, marking the first cell of each row and column that contains a zero.
• Set Rows and Columns: Use the marks to set entire rows and columns to zero.
• Handle First Row and Column: Special handling for the first row and column to avoid overriding the marks.

Conclusion

The Set Matrix Zeroes problem is a valuable exercise in in-place array manipulation. It requires careful consideration to avoid unintended side effects while modifying the matrix.

The algorithm achieves constant space complexity (O(1)) by using the first row and the first column of the matrix itself to store information about which rows and columns should be zeroed.

Here’s a breakdown of how this is achieved:

First Pass: Iterate through the matrix and use the first cell of each row and column to mark whether that row or column should be set to zero. This requires two special checks:

Determine if the first row should be set to zero based on the cells in the first row. Determine if the first column should be set to zero based on the cells in the first column. Second Pass: Use the marks in the first row and first column to set the appropriate rows and columns to zero. Skip the first row and first column in this pass.

Final Step: Based on the checks from the first step, set the first row and/or first column to zero if needed.

This approach only uses a constant amount of additional space (for variables like isCol and loop counters) and modifies the matrix in place.