Constant Space Java solution


  • 12
    S

    a b b

    b c c

    b c c

    Step1: Determine row1 and col1. Need to go through the first col and first row. Use two vars to store that information.
    Step2: Use "c" to determine "b". Need to go through the entire matrix. Once "c" is zero, set its corresponding two "b"s to zero.
    Step3: Use "b" to set "c". If "b" is zero, its corresponding row or col are set to all zero.
    Step4: Use previous row1 and col1 information to set col1 and row1.

    public class Solution {
        public void setZeroes(int[][] matrix) {
            boolean firstColZero = false, firstRowZero = false;
            for(int i = 0;i < matrix.length;i++)
                if(matrix[i][0] == 0)
                    firstColZero = true;
            for(int j = 0;j < matrix[0].length;j++)
                if(matrix[0][j] == 0)
                    firstRowZero = true;
            for(int i = 1;i < matrix.length;i++)
                for(int j = 1;j < matrix[0].length;j++)
                    if(matrix[i][j] == 0)
                        matrix[i][0] = matrix[0][j] = 0;
            for(int i = 1;i < matrix.length;i++)
                if(matrix[i][0] == 0)
                    for(int j = 0;j < matrix[0].length;j++)
                        matrix[i][j] = 0;
            for(int j = 1;j < matrix[0].length;j++)
                if(matrix[0][j] == 0)
                    for(int i = 0;i < matrix.length;i++)
                        matrix[i][j] = 0;
            if(firstColZero)
                for(int i = 0;i < matrix.length;i++)
                    matrix[i][0] = 0;
            if(firstRowZero)
                for(int j = 0;j < matrix[0].length;j++)
                    matrix[0][j] = 0;
                    
        }
    }

  • 2
    S

    a very smart solution, using 2 boolean mark if row0 and col0 has 0, then using row0 and col0 as the marker, for other rows and cols. It reduced the extra space O(N + M). bravo!


  • 0
    J

    try to use break inside the first two loops. and also, too many loops, could be more concise.


Log in to reply
 

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