Cracking the Code Interview (Gayle McDowell) Solution


  • 0
    D
    public void setZeroes(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            boolean firstRowHasZero = false, firstColHasZero = false;
            for(int i=0; i<n; i++) {
                if(matrix[0][i] == 0) {
                    firstRowHasZero = true;
                    break;
                }
            }
            for(int i=0; i<m; i++) {
                if(matrix[i][0] == 0) {
                    firstColHasZero = true;
                    break;
                }
            }
            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;
                        
                    }
                }
            }
            
            for(int i=1; i<n; i++) {
                if(matrix[0][i] == 0) fillColWithZeroes(i,matrix);
            }
            for(int i=1; i<m; i++) {
                if(matrix[i][0] == 0) fillRowWithZeroes(i,matrix);
            }
            if(firstRowHasZero)
                fillRowWithZeroes(0,matrix);
            if(firstColHasZero)
                fillColWithZeroes(0,matrix);
        }
        private void fillRowWithZeroes(int row,int [][]matrix) {
            for(int i=0; i<matrix[0].length; i++)
                matrix[row][i] = 0;
        }
        private void fillColWithZeroes(int col,int [][]matrix) {
            for(int i=0; i<matrix.length; i++)
                matrix[i][col] = 0;
        }

  • 0
    D
        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;
    
                }
            }
        }
    

    shouldn't the index start with 0 ?


  • 0
    D

    Here, we use the first row and the first column to know which rows and columns have zeros. Finally, we can maintain the first row and the first column. You can check the whole solution in Cracking the Code Interview textbook.


  • 0
    T

    This should be in the question, why is it a separate answer?


  • 0
    T

    first (0th) row and column is used for marking if the whole row/column has any zeroes, it doesn't matter what their values are in this doulbe loop, because we checked those indices in the earlier two loops and when setting the zeroes they're not set to avoid collision, hence the two extra fiil*WithZeroes calls.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.