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.

Follow up:

• 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?

Approach1: brute-force

Although this approach is the least optimal, it is very intuitive.

• We iterate over each elelement of the matrix.

• As loop progesses, if element equals zero we set that respective element's row and column to 0.

We realize that implementing a method which strictly follows the aforementionned is erroneous as our matrix ends up consisting only of 0's. To avoid this caveat, we also implement the below.

• We need to make sure that we use a boolean matrix of identical size to the original matrix. That boolean matrix will track elements that were intially zeroes as well as the one's that are now zeroes as the loop progresses.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[][]changed = new boolean[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0 && !changed[i][j]){
                    
                    for(int k = 0; k < n; k++){
                        if(matrix[i][k] != 0){
                            matrix[i][k] = 0;
                            changed[i][k] = true;
                        }
                    }
                    for(int k = 0; k < m; k++){
                        if(matrix[k][j] != 0){
                            matrix[k][j] = 0;
                            changed[k][j] = true;
                        }
                    }
                }
            }
        }
    }
}

Time: O(mn) Space: O(mn)

Approach2 : Less Memory Approach

We notice that we can better our approach by simply recording the row and column for which there was an elemt that was equal to zero. Then, in a next iteration, we simply ensure that the pertinent cells are marked zero.

• We iterate over the array and look for zero entries

• if we find that element [i, j] is 0, we record i as well j

• we use two sets, one for the rows and one for the columns.

• Finally, we iterate over the original matrix. For every cell we check if the row r or column c exist within one of the sets. If any of them is true, we set the value in the cell to 0.

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> setX = new HashSet<>();
        Set<Integer> setY = new HashSet<>();
        
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if(matrix[i][j] == 0){
                    setX.add(i);
                    setY.add(j);
                }
            }
        }
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                if(setX.contains(i) || setY.contains(j))
                   matrix[i][j] = 0;
            }
        }
    }
}

Time: O(m + n) Space: O(m + n)

Approach3 : Optimal

The optimization in this approach lies in using the first row and first column to be used as idexes to signal whether or not there needs to be a reset to 0.

• 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; (using boolean variables)

• And because you are altering first row and collumn, 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)_

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRow = false, firstColumn = false;
        int m = matrix.length, n = matrix[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    if(i == 0) firstRow = true;
                    if(j == 0) firstColumn = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        if(firstRow){
            for(int i = 0; i < n; i++){
                matrix[0][i] = 0;
            }
        }
        if(firstColumn){
            for(int j = 0; j < m; j++){
                matrix[j][0] = 0;
            }
        }
    }
}

Time: O(m + n) Space: O(1)