Set Matrix Zeroes

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

For Example:

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

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

Explanation: As the matrix[0][1] is 0 in the input matrix, so the 0th row and 1st column is set to Zero in the resulting matrix.

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1
Set Matrix to Zero

We can use the first row and first column of the matrix to store the status of the rows and columns respectively. The problem will occur for the status of first row and column which can be handled using two variables which will store the status of the first row and column.

Algorithm

  1. Initialize row and column to false. These two variables will store the status of the first row and first column.
  2. Now use the first row and first column as your hash which stores the status of that row and column.
  3. Now iterate over the matrix and for every A[i][j] == 0, set A[i][0] = 0 and col[0][j] = 0.
  4. Now update the values of the matrix except first row and first column to 0 if A[i][0]= 0 or A[0][i] = 0 .
  5. Now update the values of the first row and first column.
class Solution {
    public void setZeroes(int[][] matrix) {
        
        boolean firstRowZero = false;
        boolean firstColumnZero = false;
        
        for(int i = 0 ; i < matrix[0].length ; i++){
            if(matrix[0][i] == 0){
                firstRowZero = true;
                break;
            }
        }
        
        for(int i = 0 ; i < matrix.length ; i++){
            if(matrix[i][0] == 0){
                firstColumnZero = 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[i][0] = 0;
                    matrix[0][j] = 0;
                }
            } 
        }
        
        for(int i = 1 ; i < matrix.length ; i++){
            for(int j = 1 ; j < matrix[0].length ; j++){
                if(matrix[0][j] == 0 || matrix[i][0] == 0){
                    matrix[i][j] = 0;
                }
            } 
        }
        
        if(firstRowZero){
            for(int i = 0 ; i < matrix[0].length ; i++){
                matrix[0][i] = 0;
            }
        }
        
         if(firstColumnZero){
            for(int i = 0 ; i < matrix.length ; i++){
                matrix[i][0] = 0;
            }
        }
    }
}

Complexity Analysis

  • Time Complexity : O(M×N)
  • Space Complexity : O(1)

Categories: 2D Array, Array

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