Row Column Zero Editorial

Practice Problem Link: Row Column Zero | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a matrix, if any of the cells in the matrix is 0, set all the elements in its row and column to 0.

Naive Approach

Here, we can store all the row and column indexes of the cells which have 0 in them, in an appropriate container. Later, we can iterate over all elements in the matrix and if the element’s row or column number is found in the set, we can change it to 0.

Analysis

• Time Complexity: O(row_size * column_size)
• Space Complexity: O(row_size + column_size) // using set or maps.

Implementation

C++

void setRowColumnZeroes(vector<vector<int> > &matrix) {
   unordered_set<int> row, col;
   int row_size = matrix.size();
   int col_size = matrix[0].size();
   for (int i = 0; i < row_size; i++) {
       for (int j = 0; j < col_size; j++) {
           if(matrix[i][j] == 0) {
               row.insert(i);
               col.insert(j);
           }
       }
   }
   for (int i = 0; i < row_size; i++) {
       for (int j = 0; j < col_size; j++) {
           if(row.find(i) != row.end()) {
               matrix[i][j] = 0;
           }
       }
   }
   for (int i = 0; i < row_size; i++) {
       for (int j = 0; j < col_size; j++) {
           if(col.find(j) != col.end()) {
               matrix[i][j] = 0;
           }
       }
   }
}

Java

class Solution {
   void setRowColumnZeroes(int[][] matrix){
       Set<Integer>  row = new TreeSet<>();
       Set<Integer> col = new TreeSet<>();
       int row_size = matrix.length;
       int col_size = matrix[0].length;
       for (int i = 0; i < row_size; i++) {
           for (int j = 0; j < col_size; j++) {
               if(matrix[i][j] == 0) {
                   row.add(i);
                   col.add(j);
               }
           }
       }
       for (int i = 0; i < row_size; i++) {
           for (int j = 0; j < col_size; j++) {
               if(row.contains(i) == true) {
                   matrix[i][j] = 0;
               }
           }
       }
       for (int i = 0; i < row_size; i++) {
           for (int j = 0; j < col_size; j++) {
               if(col.contains(j) == true) {
                   matrix[i][j] = 0;
               }
           }
       }
   }
}

Optimal Approach

We cannot optimize the time complexity any further in this problem, since at all costs we need to traverse the matrix at least once to get the positions of the zeroes in it. However, we can optimize the space complexity to make the program use constant space.

The key idea here is that rather than using additional variables to keep track of the rows and columns to be reset, we can directly use the original matrix itself to keep track of the changes to be made.

We can use the first cell of every row and column as a flag, which would determine whether a row or column has been set to zero or not. So, for every cell, from going to row_size + col_size cells, we can only set the flag at 2 cells only. In another pass, we can use these flags to update the matrix accordingly in constant space.

Analysis

• Time Complexity: O(row_size * column_size)
• Space Complexity: O(1)

Implementation

C++

void fillRowWithZero(vector<vector<int> > &matrix, int index, int row_size) {
   for (int i = 0; i < row_size; i++) {
       matrix[index][i] = 0;
   }
}
void fillColumnWithZero(vector<vector<int> > &matrix, int index, int col_size){
   for (int i = 0; i < col_size; i++) {
       matrix[i][index] = 0;
   }
}
void setRowColumnZeroes(vector<vector<int> > &matrix) {
   int row_size = matrix.size();
   int col_size = matrix[0].size();
   bool topRowZero = false, leftColumnZero = false;
   for (int i = 0; i < row_size; i++) {
       for (int j = 0; j < col_size; j++) {
           if(matrix[i][j] == 0) {
               if(i == 0 && j == 0) {
                   topRowZero = true;
                   leftColumnZero = true;
               } else if(j == 0) {
                   leftColumnZero = true;
                   matrix[i][0] = 0;
               } else if(i == 0) {
                   topRowZero = true;
                   matrix[0][j] = 0;
               } else {
                   matrix[i][0] = 0;
                   matrix[0][j] = 0;
               }
           }
       }
   }
   for (int i = 1; i < col_size; i++) {
       if(matrix[0][i] == 0) {
           fillColumnWithZero(matrix, i, row_size);
       }
   }
   for (int i = 1; i < row_size; i++) {
       if(matrix[i][0] == 0) {
           fillRowWithZero(matrix, i, col_size);
       }
   }
   if(topRowZero) {
       fillRowWithZero(matrix, 0, col_size);
   }
   if(leftColumnZero) {
       fillColumnWithZero(matrix, 0, row_size);
   }
}

Java

class Solution {
   void fillRowWithZero(int[][] matrix, int index, int row_size) {
       for(int i = 0 ;i < row_size ;i++) {
           matrix[index][i] = 0;
       }
   }
   void fillColumnWithZero(int[][] matrix, int index, int col_size) {
       for(int i = 0;i < col_size; i++) {
           matrix[i][index] = 0;
       }
   }
   void setRowColumnZeroes(int[][] matrix){
       int row_size = matrix.length;
       int col_size = matrix[0].length;
       boolean topRowZero = false, leftColumnZero = false;
       for (int i = 0; i < row_size; i++) {
           for (int j = 0; j < col_size; j++) {
               if(matrix[i][j] == 0) {
                   if(i == 0 && j == 0) {
                       topRowZero = true;
                       leftColumnZero = true;
                   } else if(j == 0) {
                       leftColumnZero = true;
                       matrix[i][0] = 0;
                   } else if(i == 0) {
                       topRowZero = true;
                       matrix[0][j] = 0;
                   } else {
                       matrix[i][0] = 0;
                       matrix[0][j] = 0;
                   }
               }
           }
       }
       for (int i = 1; i < col_size; i++) {
           if(matrix[0][i] == 0) {
               fillColumnWithZero(matrix, i, row_size);
           }
       }
       for(int i = 1; i < row_size; i++) {
           if(matrix[i][0] == 0) {
               fillRowWithZero(matrix, i, col_size);
           }
       }
       if(topRowZero == true) {
           fillRowWithZero(matrix, 0, col_size);
       }
       if(leftColumnZero == true) {
           fillColumnWithZero(matrix, 0, row_size);
       }
   }
}