Leetcode: Set Matrix Zeroes (84ms) analysis & solution

PROBLEM:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Hide Tags

 Array

Analysis:

The key is how to use O(1) space to solve it. 

A general method is to use the first row and first column to mark the 0 which appear in the related column/row. And use additional two flags to mark whether there are 0 in first row/column. After marking, set all columns / rows to zero based on the previous marks on first row and first column and the flags. 

The whole procedure is shown in following figure:

/////////////////////////////////////////////////////////////////////

//code 84ms

class Solution {

public:

       void setZeroes(vector<vector<int>>& matrix) {

              int raw_flag = 0, col_flag = 0, m = matrix.size(), n = matrix[0].size();

              //set flags for first column and first row

              for (int i = 0; i<m; i++){

                     for (int j = 0; j<n; j++){

                           if (matrix[i][j] == 0){

                                  if (i == 0 && j == 0){

                                         raw_flag = 1; col_flag = 1;

                                  }

                                  else if (i == 0)col_flag = 1;

                                  else if (j == 0)raw_flag = 1;

                                  else {

                                         matrix[0][j] = 0;

                                         matrix[i][0] = 0;

                                  }

                           }

                     }

              }

              //set zeros for row

              for (int i = 1; i<m; i++){

                     if (matrix[i][0] == 0){

                           for (int ii = 0; ii<n; ii++)matrix[i][ii] = 0;

                     }

              }

              //set zero for colom

              for (int j = 1; j<n; j++){

                     if (matrix[0][j] == 0){

                           for (int jj = 0; jj<m; jj++)matrix[jj][j] = 0;

                     }

              }

              //set zeros for first column

              if (raw_flag == 1){

                     for (int ii = 0; ii<m; ii++)matrix[ii][0] = 0;

              }

              //set zero for first row

              if (col_flag == 1){

                     for (int ii = 0; ii<n; ii++)matrix[0][ii] = 0;

              }

       }

};