Set Matrix Zeroes - Leetcode Solution

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

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

Solution: The brute force solution to set the rows and columns of an array to zero is to create a set of rows and columns to collect the zeros and then iterate through the matrix once more to set all the zeros in the set to zero.

We can optimize this approach by reducing the space complexity from O(m+n) to O(1) by using the first row and column as our sets as they can be later used to set the zeros in the matrix.

Approach:

1. Initialize two variables to keep track of whether the first row and column have any zeros.
2. Iterate through the matrix and if the element is zero, set the corresponding element in the first row and column to zero.
3. Iterate through the first row and column and if an element is zero, set the corresponding row and column in the matrix to zero.
4. If step 1 is true, set all elements in the first row to zero.
5. If step 2 is true, set all elements in the first column to zero.
6. Return the modified matrix.

Code:

class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean firstRowZero = false; boolean firstColZero = false;

    // check if first row has zeros
    for(int j=0; j<n; j++) {
        if(matrix[0][j] == 0) {
            firstRowZero = true;
            break;
        }
    }
    
    // check if first column has zeros
    for(int i=0; i<m; i++) {
        if(matrix[i][0] == 0) {
            firstColZero = true;
            break;
        }
    }
    
    // check the matrix and if zero is there then set zero to corresponding cell in first row and column
    for(int i=1; i<m; i++) {
        for(int j=1; j<n; j++) {
            if(matrix[i][j] == 0) {
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    
    // set corresponding rows and columns to zero
    for(int i=1; i<m; i++) {
        for(int j=1; j<n; j++) {
            if(matrix[0][j] == 0 || matrix[i][0] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    
    // set the first row to zeros if required
    if(firstRowZero) {
        for(int j=0; j<n; j++) {
            matrix[0][j] = 0;
        }
    }
    
    // set the first col to zeros if required
    if(firstColZero) {
        for(int i=0; i<m; i++) {
            matrix[i][0] = 0;
        }
    }
}

}

Complexity Analysis: The time complexity is O(m*n) as we are iterating through the array twice.
The space complexity is O(1) as we are only using two boolean variables to store information about the first row and column.

1