Very clean solution O(1) space (without messing around with the given matrix e.g using some row and col to store states)


  • -2
    B
    public void setZeroes(int[][] matrix) {
      boolean zeroPrevRow = false;
      for(int i = 0; i <= matrix.length; i++) {
        boolean zeroRow = false;
        if(i < matrix.length) {
          int[] row = matrix[i];
          for(int j = 0; j < row.length; j++) {
            if(row[j] == 0)
              zeroRow = true;
            if(i != 0) {
              if(matrix[i - 1][j] == 0)
                row[j] = 0;
              else if(row[j] == 0) {
                for(int k = 0; k < i; k++)
                  matrix[k][j] = 0;
              }
            }
          }
        }
        if(zeroPrevRow) {
          int[] prevRow = matrix[i - 1];
          Arrays.fill(prevRow, 0);
        }
        zeroPrevRow = zeroRow;
      }
    }
    

    idea is very simple:

    if row i needs to be zeroed, delay the zeroing until i + 1.

    it runs faster than the average as well, since there is only one m * n loop. I think the average solution use 2 m * n loops.


  • -1
    L

    But it is not the O(1) space,,,use
    int[] row = matrix[i];
    and
    int[] prevRow = matrix[i - 1];


  • 0
    F

    that's implementation specific: if using pointers, it is O(1) since it avoids copying.


  • 0
    Q

    That's correct. It's O(1). He/she is simply creating 2 references in his/her java code. Could have easily done without that so not to confuse people who don't know Java.


Log in to reply
 

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