2014.2.13 22:15

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

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?

Solution1:

　　The O(m * n) solution is unacceptable and unnecessary, so we'll write the O(m + n) version first.

　　The extra O(n) and O(m) spaces are used to mark if this row or column contains 0.

　　Code is relatively simple, please see for yourself.

　　Time complexity is O(n * m), space complexity is O(n + m).

Accepted code:

1 // 1AC, O(m + n) solution. 2 class Solution { 3 public: 4     void setZeroes(vector
     
      
        > &matrix) { 5         int n, m; 6          7         n = matrix.size(); 8         if (n == 0) { 9             return;10         }11         m = matrix[0].size();12         if (m == 0) {13             return;14         }15 16         int i, j;17         vector
       
         row_zero, col_zero;18         19         for (i = 0; i < n; ++i) {20             row_zero.push_back(0);21         }22         for (j = 0; j < m; ++j) {23             col_zero.push_back(0);24         }25         26         for (i = 0; i < n; ++i) {27             for (j = 0; j < m; ++j) {28                 if (matrix[i][j] == 0) {29                     row_zero[i] = 1;30                     col_zero[j] = 1;31                 }32             }33         }34         35         for (i = 0; i < n; ++i) {36             if (row_zero[i]) {37                 for (j = 0; j < m; ++j) {38                     matrix[i][j] = 0;39                 }40             }41         }42         43         for (j = 0; j < m; ++j) {44             if (col_zero[j]) {45                 for (i = 0; i < n; ++i) {46                     matrix[i][j] = 0;47                 }48             }49         }50         51         row_zero.clear();52         col_zero.clear();53     }54 };
       
      
     

Solution2:

　　Since the problem requires an algorithm using O(1) space, we'll have to improve the previous version.

　　The matrix itself takes O(n * m) space, so we might take one row and one column from it as the marker array.

　　With one row and column picked out as marker array, we'll need two extra markers for this row and column. Let them be the first row and first column.

　　The code will be longer, with the 1st and 2st~nth rows processed separately, likewise for columns.

　　Time complexity is O(n * m), space complexity is O(1).

Accepted code:

1 // 1WA, 1AC, use the first row and column as markers. 2 class Solution { 3 public: 4     void setZeroes(vector
     
      
        > &matrix) { 5         int n, m; 6          7         n = matrix.size(); 8         if (n == 0) { 9             return;10         }11         m = matrix[0].size();12         if (m == 0) {13             return;14         }15 16         bool c0_is_zero, r0_is_zero;17         int i, j;18         19         c0_is_zero = false;20         for (i = 0; i < n; ++i) {21             if (matrix[i][0] == 0) {22                 c0_is_zero = true;23                 break;24             }25         }26         27         r0_is_zero = false;28         for (i = 0; i < m; ++i) {29             if (matrix[0][i] == 0) {30                 r0_is_zero = true;31                 break;32             }33         }34         35         for (i = 1; i < n; ++i) {36             for (j = 1; j < m; ++j) {37                 if (matrix[i][j] == 0) {38                     // use 0th row and column as markers39                     matrix[i][0] = 0;40                     matrix[0][j] = 0;41                 }42             }43         }44         45         for (i = 1; i < n; ++i) {46             if (matrix[i][0] == 0) {47                 for (j = 1; j < m; ++j) {48                     matrix[i][j] = 0;49                 }50             }51         }52         53         for (j = 1; j < m; ++j) {54             if (matrix[0][j] == 0) {55                 for (i = 1; i < n; ++i) {56                     matrix[i][j] = 0;57                 }58             }59         }60         61         if (r0_is_zero) {62             for (j = 0; j < m; ++j) {63                 matrix[0][j] = 0;64             }65         }66         if (c0_is_zero) {67             for (i = 0; i < n; ++i) {68                 matrix[i][0] = 0;69             }70         }71     }72 };