Java 2 solutions: space O(1) and O(m+n), with explaination


  • 2
    M

    space O(1), time O(mn)
    Use the top row and the left column to record which rows and columns need to be set 0. topZero and leftZero to record whether we need to set the top row and the left column to zero before finished.

        public void setZeroes(int[][] matrix) {
            if(matrix==null) return;
            final int M=matrix.length, N=matrix[0].length;
            boolean topZero=false, leftZero=false;
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(matrix[i][j]==0){
                        if(i==0) topZero = true;
                        if(j==0) leftZero = true;
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            for(int i=1; i<M; i++){
                if(matrix[i][0]==0){
                    for(int q=1; q<N; q++) matrix[i][q] = 0;
                }
            }
            for(int j=1; j<N; j++){
                if(matrix[0][j]==0){
                    for(int p=1; p<M; p++)  matrix[p][j] = 0;
                }
            }
            if(topZero){
                for(int q=0; q<N; q++) matrix[0][q] = 0;
            }
            if(leftZero){
                for(int p=0; p<M; p++) matrix[p][0] = 0;
            }
        }
    

    space O(m+n), time O(mn)

        public void setZeroes_Set(int[][] matrix) {
            if(matrix==null) return;
            final int M=matrix.length, N=matrix[0].length;
            Set<Integer> rowSet = new HashSet<>();
            Set<Integer> colSet = new HashSet<>();
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(matrix[i][j]==0){
                        rowSet.add(i);
                        colSet.add(j);
                    }
                }
            }
            for(int row : rowSet)
                for(int j=0; j<N; j++)
                    matrix[row][j] = 0;
            for(int col : colSet)
                for(int i=0; i<M; i++)
                    matrix[i][col] = 0;
        }
    

Log in to reply
 

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