73. Set Matrix Zeroes Leetcode Java

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

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Solution:

As the problem addressed, it is not hard to find a solution with extra space, but a constant space solution is more challenging. 

In order to avoid using extra space, we have to make a good use of the matrix itself.

We can use one row and one column as a flag array to store the required information and then take care of the picked flag row and column after processing the whole matrix.

Usually, we pick the first row and first column, first we check if the first row and the first column contains a 0 element, we use two boolean variables to record if they are needed to be set to 0. After that, we transverse the whole matrix(except the first row and column), if there is 0 element, set the corresponding element in first row and first column to 0. Eg if matrix[i][j]=0, set matrix[0][j] and matrix[i][0] as 0.

Then we have all the rows and columns that need to be set. Transverse the matrix again(except the first row and column), set element to 0 according to the information we stored in the first row and column. After that, we then set the first row and first column to zero if needed according to two boolean variables.

Time complexity: O(m*n) constant space.

  public void setZeroes(int[][] matrix) {  
     if(matrix==null || matrix.length==0 || matrix[0].length==0) return;  
     boolean row=false;  
     boolean column=false;  
     for(int i=0;i<matrix.length;i++){  
       if(matrix[i][0]==0){  
         column=true;  
         break;  
       }  
     }  
     for(int j=0;j<matrix[0].length;j++){  
       if(matrix[0][j]==0){  
         row=true;  
         break;  
       }  
     }  
     for(int i=1;i<matrix.length;i++){  
       for(int j=1;j<matrix[0].length;j++){  
         if(matrix[i][j]==0){  
           matrix[0][j]=0;  
           matrix[i][0]=0;  
         }  
       }  
     }  
     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;  
       }  
     }  
     if(row){  
       for(int j=0;j<matrix[0].length;j++) matrix[0][j]=0;  
     }  
     if(column){  
       for(int i=0;i<matrix.length;i++) matrix[i][0]=0;  
     }  
   }