Set Matrix to Zeroes

Set Matrix to Zeroes

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

As we go through the matrix, if we find a zero, we cannot set its row and column to zeroes yet. If we do that, we would not know whether or not to set the next row and next column to zeroes.

So, we iterate through the matrix twice.
In the first iteration, we find out all of the zeroes and store their row and column numbers.
In the next iteration, we set a cell to zero if it is on a row or a column that we stored.

public void setZeroes(int[][] matrix) {  
   Set rows = new HashSet();  
   Set columns = new HashSet();  
   
   // find zeroes  
   for (int i = 0; i < matrix.length; ++i) {  
     for (int j = 0; j < matrix[0].length; ++j) {  
       if (matrix[i][j] == 0) {  
         rows.add(i);  
         columns.add(j);  
       }  
     }  
   }  
   
   // set zeroes  
   for (int i = 0; i < matrix.length; ++i) {  
     for (int j = 0; j < matrix[0].length; ++j) {  
       if (rows.contains(i) || columns.contains(j)) matrix[i][j] = 0;  
     }  
   }  
 }  

Can we do it in-place?

We have an entire matrix and thus we can use one row and one column of the matrix to store the zero information. Before we revise the values in that row and column, we need to know whether the original row/column contain zero. If so, we also need to set the row/column to zeros; If not, leave other values as they are.

public void setZeroes(int[][] matrix) {  
   int rownum = matrix.length;  
   if (rownum == 0) return;  
   int colnum = matrix[0].length;  
   if (colnum == 0) return;  
   
   boolean hasZeroFirstRow = false, hasZeroFirstColumn = false;  
   
   // Does first row have zero?  
   for (int j = 0; j < colnum; ++j) {  
     if (matrix[0][j] == 0) {  
       hasZeroFirstRow = true;  
       break;  
     }  
   }  
   
   // Does first column have zero?  
   for (int i = 0; i < rownum; ++i) {  
     if (matrix[i][0] == 0) {  
       hasZeroFirstColumn = true;  
       break;  
     }  
   }  
   
   // find zeroes and store the info in first row and column  
   for (int i = 1; i < matrix.length; ++i) {  
     for (int j = 1; j < matrix[0].length; ++j) {  
       if (matrix[i][j] == 0) {  
         matrix[i][0] = 0;  
         matrix[0][j] = 0;  
       }  
     }  
   }  
   
   // set zeroes except the first row and column  
   for (int i = 1; i < matrix.length; ++i) {  
     for (int j = 1; j < matrix[0].length; ++j) {  
       if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;  
     }  
   }  
   
   // set zeroes for first row and column if needed  
   if (hasZeroFirstRow) {  
     for (int j = 0; j < colnum; ++j) {  
       matrix[0][j] = 0;  
     }  
   }  
   if (hasZeroFirstColumn) {  
     for (int i = 0; i < rownum; ++i) {  
       matrix[i][0] = 0;  
     }  
   }  
 }  

Leave a Reply

Your email address will not be published. Required fields are marked *