SetMatrixZeros.java

public class SetMatrixZeros {
    public void setZeroes(int[][] matrix) {
        if(matrix == null) return;
        if(matrix.length == 0) return;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        boolean[] rows = new boolean[m];
        boolean[] cols = new boolean[n];
        
        for(int i = 0 ; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    rows[i] = true;
                    cols[j] = true;
                }
            }
        }
        
        for(int i = 0; i < m; i++){
            if(rows[i]){
                for(int j = 0; j < n; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        
        for(int j = 0; j < n; j++){
            if(cols[j]){
                for(int i = 0; i < m; i++){
                    matrix[i][j] = 0;
                }
            }
        }
    }
    
    public void setZeroes2(int[][] matrix) {
        if(matrix == null) return;
        if(matrix.length == 0) return;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        boolean hasZeroOnFirstRow = false;
        boolean hasZeroOnFirstColumn = false;
        
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0){
                hasZeroOnFirstColumn = true;
                break;
            }
        }
        
        for(int j = 0; j < n; j++){
            if(matrix[0][j] == 0){
                hasZeroOnFirstRow = true;
                break;
            }
        }
        
        // step 2, check other cells
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // now we set the rows and columns to zeros
        // remember that first row and column records the occurrence of zeros
        // in matrix[1:m][1:n]. Therefore, we can only use them to change 
        // the cells in matrix[1:m][1:n]
        for(int i = 1; i < m; i++){
            if(matrix[i][0] == 0){
                for(int j = 1; j < n; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        
        for(int j = 1; j < n; j++){
            if(matrix[0][j] == 0){
                for(int i = 1; i < m; i++){
                    matrix[i][j] = 0;
                }
            }
        }
        
        // do not forget the first row and column
        if(hasZeroOnFirstRow){
            for(int j = 0; j < n; j++){
                matrix[0][j] = 0;
            }
        }
        
        if(hasZeroOnFirstColumn){
            for(int i = 0; i < m; i++){
                matrix[i][0] = 0;
            }
        }
    }
}