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.

click to show follow up.

Follow up:

Did you use extra space?
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?

Solution1: use two arrays to keep track of all the rows with zeros and all the columns with zeros. We then make a second pass of the matrix and set a cell to zero if its row or column is zero.

public class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] row = new boolean[matrix.length];
        boolean[] col = new boolean[matrix[0].length];
        
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(row[i] == true || col[j] == true)
                    matrix[i][j] = 0;
            }
        }
    }
}

Solution2: 不需要额外空间 1. check if first row and column are zero or not. 2. mark zeros on first row and column 3. use mark to set elements 4. set first column and row by using marks in step 1.
Run time complexity is O(n^2), constant space.

public class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        
        boolean row0Zero = false;
        boolean col0Zero = false;
        
        //use first row and column as storage
        //1.search zero in first row and col to determin it's own status
        for(int i = 0; i < row; i++) {
            if(matrix[i][0] == 0) {
                col0Zero = true;
                break;
            }
        }
        for(int i = 0; i < col; i++) {
            if(matrix[0][i] == 0) {
                row0Zero = true;
                break;
            }
        }
        
        //2.search zeros in other position to sign the first row and col
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                if(matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        //3.set zeroes in other positions according to first col and row
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }
        
        //4.set zeroes for first row and col
        if(col0Zero) {
            for(int i = 0; i < row; i++)
                matrix[i][0] = 0;
        }
        if(row0Zero) {
            for(int i = 0; i < col; i++)
                matrix[0][i] = 0;
        }
        
    }
}