This problem can be solved easily if we are allowed to use more than O(1) space. For example, you may create a copy of the original matrix (O(mn)-space) or just record the row and column indexes (O(m + n)-space). Well, is there a O(1)-space solution? Yes, you may refer to this link :-)
The key idea is to record the rows and columns that need to be set to zeroes directly in the matrix ( if (!matrix[i][j]) matrix[i][0] = matrix[0][j] = 0; ). The code is rewritten as follows.
1 class Solution { 2 public: 3 void setZeroes(vector<vector<int>>& matrix) { 4 int m = matrix.size(), n = matrix[0].size(); 5 bool c0 = false; 6 for (int i = 0; i < m; i++) { 7 if (!matrix[i][0]) c0 = true; 8 for (int j = 1; j < n; j++) 9 if (!matrix[i][j]) matrix[i][0] = matrix[0][j] = 0; 10 } 11 for (int i = m - 1; i >= 0; i--) { 12 for (int j = n - 1; j; j--) 13 if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0; 14 if (c0) matrix[i][0] = 0; 15 } 16 } 17 };
