Set Matrix Zeroes

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

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

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

Solution

Code Explanation

     fr = first row
     fc = first col
    
     Use first row and first column as markers. 

     if matrix[i][j] = 0, mark respected row and col marker = 0; indicating
       that later this respective row and col must be marked 0;

     And because you are altering first row and column, 
       you need to  have two variables to track their own status. 

     So, for ex, if any one of the first row is 0, fr = 0, 
       and at the end set all first row to 0;
public class Solution {
    public void SetZeroes(int[][] matrix) {
        
        bool firstRow = false, firstCol = false;
        int row = matrix.Length, col = matrix[0].Length;
        
        for(int i=0;i<row;i++){
            
            for(int j=0;j<col;j++){
                
                if(matrix[i][j] == 0){
                
                    if(i == 0)
                        firstRow = true;
                    
                    if(j == 0)
                        firstCol = true;
                    
                    matrix[0][j] = 0;
                    
                    matrix[i][0] = 0;
                }
            }
        }

         //process except the first row and column
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(matrix[0][j] == 0 || matrix[i][0] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        
        if(firstRow){
            for(int j=0;j<col;j++){
                matrix[0][j] = 0;
            }
        }
        if(firstCol){
            for(int i=0;i<row;i++){
                matrix[i][0] = 0;
            }
        }
    }
}

Time Complexity: O(m * n)

Space Complexity: O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s