King Of Interviews

Set Matrix Zeroes: Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s.

You must do it in place.

Example 1:

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

Example 2:

Input: matrix = [[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]]

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

Try this Problem on your own or check similar problems:

Solution:

public void setZeroes(int[][] matrix) {
    int rows = matrix.length, columns = matrix[0].length;
    boolean zeroFirstRow = false, zeroFirstColumn = false;

    for(int i = 0; i < columns; ++i ){
        if(matrix[0][i] == 0) zeroFirstRow = true;
    }

    for(int i = 0; i < rows; ++i){
        if(matrix[i][0] == 0) zeroFirstColumn = true;
    }

    for(int i = 1; i < rows; ++i){
        for(int j = 1; j < columns; ++j){
            if(matrix[i][j] == 0){
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }

    for(int i = 1; i < rows; ++i){
        if(matrix[i][0] == 0){
            for(int j = 0; j < columns; ++j){
                matrix[i][j] = 0;
            }
        }
    }

    for(int i = 1; i < columns; ++i){
        if(matrix[0][i] == 0){
            for(int j = 0; j < rows; ++j){
                matrix[j][i] = 0;
            }
        }
    }

    if(zeroFirstRow){
        for(int i = 0; i < columns; ++i){
            matrix[0][i] = 0;
        }
    }

    if(zeroFirstColumn){
        for(int i = 0; i < rows; ++i){
            matrix[i][0] = 0;
        }
    }
}

Time/Space Complexity:

Time Complexity: O(n*m)
Space Complexity: O(1)

Explanation:

The secret to solving most array problems in an optimal way is to reuse the input and do the transformation in place. In this problem it would be trivial if we could create a helper matrix and then iterate over the input matrix and write to our new matrix zeroes or non-zero element depending on the values in the input matrix. But can we do it in place reusing the input array/matrix? The trick is to somehow coordinate the zero writing within the matrix. We can do that easily by declaring the first row and first column as our controllers of where zeroes should be. In other words, if we find a row in matrix (other than the first row) which contains one zero the whole row must be “zeroed” so we can store that information in the first column. For the columns it’s the same story if we encounter a column with a zero the whole column must be “zeroed” so we can store that information in the first row. At the end we just use the controller row and column to write zeroes to each of the columns and rows where zeroes should be written to. Only one additional thing is important to note, we are doing destructive operations only on the first row and column (before doing the actual “zeroing”), so we first must determine if the first column and first row should be also “zeroed”. We do this with two booleans (zeroFirstRow and zeroFirstColumn) and the first two loops. Since we only iterate over two dimensions of the input array we have O(n*m) time complexity, and since we only do transformations on the input matrix we have constant space complexity.

Set Matrix Zeroes