Set Matrix Zeroes

73 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]
]

Set Matrix Zero

Problem Analysis

Can we use additional space to store the temporary results?

Algorithm Analysis

1. Record all zeros and change the rows and columns once. O(2*MN)
1. Record which zeros are changed from others and skip that zero while traversing. O(MN)
1. In place: Use first row and first column as markers. If matrix[i][j] = 0, mark respected row and col marker = 0 (matrix[0][j] = 0; matrix[i][0] = 0). And because we are altering the first row and column, we need to have two variables to track their status. So, for example, if any one of the first rows is 0, fr = 0, and at the end set all first row to 0.

Time Complexity Analysis

O(M*N)

Code Implementation - Store All zeros

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        if(row == 0) return;
        int col = matrix[0].length;
        if(col == 0) return;
        
        List<int[]> meetZeroes = new ArrayList<>();
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0) meetZeroes.add(new int[]{i,j}); 
            }
        }
        
        for(int k = 0; k < meetZeroes.size(); k++) {
            int[] zeroPos = meetZeroes.get(k);
            makeRowZeroes(matrix, zeroPos[0]);
            makeColZeroes(matrix, zeroPos[1]);
        }
    }
    
    public void makeRowZeroes(int[][] matrix, int row) {
        for(int i = 0; i < matrix[0].length; i++) {
            matrix[row][i] = 0;
        }
    }
    
    public void makeColZeroes(int[][] matrix, int col) {
        for(int i = 0; i < matrix.length; i++) {
            matrix[i][col] = 0;
        }
    }
}

Code Implementation - Store changed zeros

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        if(row == 0) return;
        int col = matrix[0].length;
        boolean[][] changed = new boolean[row][col];
        
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j++) {
                if(matrix[i][j] == 0 && !changed[i][j]) {
                    setRowZeros(i, matrix, changed);
                    setColZeros(j, matrix, changed);
                }
            }
        }
    }
    
    public void setRowZeros(int r, int[][] matrix, boolean[][] changed) {
        for(int c = 0; c < matrix[0].length; c++) {
            if(matrix[r][c] != 0) {
                matrix[r][c] = 0;
                changed[r][c] = true;
            }
        }
    }
    
    public void setColZeros(int c, int[][] matrix, boolean[][] changed) {
        for(int r = 0; r < matrix.length; r++) {
            if(matrix[r][c] != 0) {
                matrix[r][c] = 0;
                changed[r][c] = true;
            }
        }
    }
}

Follow up - Optimization (In place)

Stored the Status about have Zero or not in the fiset Col and first Row.

Then, loop through again the rest of the marix (i = 1 to row and j = 1 to col), if meet [i][0] ot [0][j] is 0 -> chagne it’s value to 0

Lately, change the first row and first col into 0 if needed.

public void setZeroes(int[][] matrix) {
    boolean fr = false,fc = false;
    for(int i = 0; i < matrix.length; i++) {
        for(int j = 0; j < matrix[0].length; j++) {
            if(matrix[i][j] == 0) {
                if(i == 0) fr = true;
                if(j == 0) fc = true;
                matrix[0][j] = 0;
                matrix[i][0] = 0;
            }
        }
    }
    for(int i = 1; i < matrix.length; i++) {
        for(int j = 1; j < matrix[0].length; j++) {
            if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    if(fr) {
        for(int j = 0; j < matrix[0].length; j++) {
            matrix[0][j] = 0;
        }
    }
    if(fc) {
        for(int i = 0; i < matrix.length; i++) {
            matrix[i][0] = 0;
        }
    }
}
    // Use first row and first column as markers. 
    // if matrix[i][j] = 0, mark respected row and col marker = 0;  
    // indicatingthat later this respective row and col 
    // must be marked 0;
    
    // 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;

Leetcode - No. 73