MATSETZERO - Editorial

editorial
1

Prerequisites: Matrix, Loops.

Problem:
Given an N x M integer matrix, if an element is 0, set its entire row and column to 0’s.

Solution Approach:

My idea is simple: store states of each row in the first of that row, and store states of each column in the first of that column. Because the state of row 0 and the state of column 0 would occupy the same cell, I let it be the state of row 0, and use another variable first_col_zero for column 0. In the first phase, use matrix elements to set states in a top-down way. In the second phase, use states to set matrix elements in a bottom-up way.

Steps in detail:

  1. Initialization: Initialize a variable first_col_zero to track if the first column contains any zeros.
  2. Detection of Zeros: Traverse through the matrix to detect zeros. If a zero is found at position (i, j), set the corresponding elements in the first row (mat[0][j]) and the first column (mat[i][0]) to zero.
  3. Setting Rows and Columns to Zero: Traverse through the matrix again, starting from the bottom-right corner. If the first row or column contains a zero (mat[i][0] == 0 or mat[0][j] == 0), set the current element to zero.
  4. Handling the First Column: After processing other columns, if first_col_zero is 0, set all elements in the first column to zero.
  5. Output: The matrix is updated with zeros according to the specified conditions.

Time Complexity:

  • Let N be the number of rows and M be the number of columns in the matrix.
  • The time complexity of the solution is O(N * M), as we traverse the entire matrix twice.

Space Complexity:

  • The space complexity is O(1), as only a few variables are used.