# 73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
- 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?
# Solution
Approach 1: Mark the zero information in the first row and column.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rowSize = matrix.size();
if (rowSize == 0)
return;
int colSize = matrix[0].size();
// Mark which row/column will be zero.
bool firstRowZero = false;
for (int col = 0; col < colSize; ++col)
{
if (matrix[0][col] == 0)
{
firstRowZero = true;
break;
}
}
for (int row = 1; row < rowSize; ++row)
{
for (int col = 0; col < colSize; ++col)
{
if (matrix[row][col] == 0)
{
matrix[row][0] = 0;
matrix[0][col] = 0;
}
}
}
// Zero the identified row/column (need to scan reversely).
for (int row = rowSize - 1; row > 0; --row)
{
for (int col = colSize - 1; col >= 0; --col)
{
if (matrix[row][0] == 0 || matrix[0][col] == 0)
matrix[row][col] = 0;
}
}
if (firstRowZero)
{
for (int col = 0; col < colSize; ++col)
matrix[0][col] = 0;
}
}
};