My O(1) java solution


  • -1
    W

    The basic idea is scan the matrix three times, the first time only mark the row be a special value if found 0, the second time only mark the column be a special if found 0, the third convert all special value to 0.

    Even though we mark the whole row/column be a special value when we found 0, it still an O(N) time complexity scan because if we found 0, we just mark the whole row/column be the special value and break immediately.

    public void setZeroes(int[][] matrix) {
            int row=matrix.length;
            if(row==0) return;
            int col=matrix[0].length;
            if(col==0) return;
            // mark rows
            for(int i=0;i<row;i++)
              for(int j=0;j<col;j++)
                if(matrix[i][j]==0){
                    for(int z=0;z<col;z++)
                      if(matrix[i][z]!=0) matrix[i][z]=Integer.MIN_VALUE/123;
                    break;
                }
           // mark by columns
           for(int i=0;i<col;i++)
              for(int j=0;j<row;j++)
                if(matrix[j][i]==0){
                    for(int z=0;z<row;z++)
                       if(matrix[z][i]!=0 && matrix[z][i]!=Integer.MIN_VALUE/123)
                         matrix[z][i]=Integer.MIN_VALUE/123;
                    break;
                }
           // convert
           for(int i=0;i<row;i++)
              for(int j=0;j<col;j++)
                 if(matrix[i][j]==Integer.MIN_VALUE/123) matrix[i][j]=0;
        }

  • 0
    Q

    This is a hack. What if your matrix has special value?


  • 0
    W

    It's actually easy to solve. You can scan the whole matrix at the beginning, find the max and the min item, then use either (max+1) or (min-1) as the special value.


  • 0
    Q

    Fair enough. You need an extra scan to pick 'special value' that is not in the matrix.


  • 0
    L

    I thought of find max and min too, but there is still problem. What if the matrix contains all the Integer? You just can't find such a unique value. This algorithm is not sound.


Log in to reply
 

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