Accepted java solution that uses space = length of single column. Only n spaces for a m*n matrix


  • 0
    S
    public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length <0)
            return;
        int[] lastRow = new int[matrix[0].length];
        //save the data fro the last row. This will be used to mark which all column need to be zeros. 
        for(int i = 0; i < matrix[0].length; i++)
        {
            lastRow[i] = matrix[matrix.length-1][i];
        }
        
        boolean isPrevRowZero = false;
    
        for(int i =0; i < matrix.length; i++)
        {
            boolean zeroflag = false;
            for(int j =0; j < matrix[0].length; j++)
            {
                if(matrix[i][j] == 0)
                {
                    zeroflag = true;
                    lastRow[j]= 0;
                }
                if(isPrevRowZero)
                {
                    matrix[i-1][j]=0;
                }
            }
            isPrevRowZero = zeroflag;
        }
        if(isPrevRowZero)
        {
            for(int i = 0; i < matrix[0].length; i++)
            {
                matrix[matrix.length-1][i] = 0;
            }
        }
        
        for(int i =0; i < lastRow.length; i++)
        {
            if(lastRow[i] == 0)
            {
                for(int j =0; j < matrix.length; j++)
                {
                    matrix[j][i]=0;
                }
            }
        }
        
    }
    }
    

    We use a matrix of length n to store which all column need to be zero. For row we dont make the rows zero immediately. When we are on next row and the previous row should be zero then while traversing current row we make the top row as zero. This save us the trouble of going back and forth.

    Last row in matrix will either be zero or not. So we do that separately. Once that is done we look at our LastRow array and start putting zeros in required columns.


Log in to reply
 

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