O(1) space java solution


  • 4
    F
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0)    return;
        int m = matrix.length, n = matrix[0].length;
        boolean row = false, col = false;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0){
                    if(i == 0)
                        row = true;
                    else if(j == 0)
                        col = true;
                    else{
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
        for(int i=m-1;i>=0;i--)
            for(int j=n-1;j>=0;j--)
                if(i == 0 && row == true || j == 0 && col == true || matrix[0][j] == 0 || matrix[i][0] == 0 )
                    matrix[i][j] = 0;
        return;
    }

  • 0
    D

    O(1) solution with the first cross as storage place.

    public class Solution {
        public void setZeroes(int[][] matrix) {
            int rowCount = matrix.length;
            int columnCount = matrix[0].length;
            int firstZeroRow = 0, firstZeroColumn = 0;
            boolean foundFirst = false;
            
            // find the first zero, use the corss 
            // formed by its column & row as storage place
            for(int row = rowCount - 1; row >= 0; row --){
                for(int column = columnCount - 1; column >= 0; column --){
                    if(matrix[row][column] == 0){
                        if(!foundFirst){
                            foundFirst = true;
                            firstZeroRow = row;
                            firstZeroColumn = column;
                        } else{
                            matrix[row][firstZeroColumn] = 0;
                            matrix[firstZeroRow][column] = 0; 
                        }
                    }
                }
            }
            if(!foundFirst){
                return;
            }
            
            // skip (firstZeroRow,firstZeroColumn) for now. 
            // Otherwise all info stored on the cross will be wiped out
            matrix[firstZeroRow][firstZeroColumn] = 1;
    
            // clean rows according to info stored on the first cross
            for(int row = rowCount - 1; row >= 0; row --){
                if(matrix[row][firstZeroColumn] == 0){
                    for(int i = columnCount - 1; i >= 0; i --){
                        matrix[row][i] = 0;
                    }
                }
            }
            
            // clean columns according to info stored on the first cross
            for(int column = columnCount - 1; column >= 0; column --){
                if(matrix[firstZeroRow][column] == 0){
                    for(int i = rowCount - 1; i >= 0; i --){
                        matrix[i][column] = 0;
                    }
                }
            }
    
            // now deal with the first cross
            for(int row = rowCount - 1; row >= 0; row --){
                matrix[row][firstZeroColumn] = 0;
            }
            for(int column = columnCount - 1; column >= 0; column --){
                matrix[firstZeroRow][column] = 0;
            }
        }
    }

Log in to reply
 

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