73. Set Matrix Zeroes
1. Description
Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
2. 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?
3. Example
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[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]]
4. Constraints
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- $-2^{31}$ <= matrix[i][j] <= $2^{31} - 1$
5. Solutions
5.1 Use the First Row and Column as Symbols(Follow Up)
n is the number of elements in m_matrix
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
void setZeroes(vector<vector<int>>& m_matrix) {
bool first_column_has_zero = false;
for(int i = 0; i < m_matrix.size(); ++i) {
if(m_matrix[i][0] == 0) {
first_column_has_zero = true;
}
for(int j = 1; j < m_matrix[0].size(); ++j) {
if(m_matrix[i][j] == 0) {
m_matrix[i][0] = m_matrix[0][j] = 0;
}
}
}
for(int i = m_matrix.size() - 1; i >= 0; --i)
{
for(int j = 1; j < m_matrix[0].size(); ++j)
{
if(m_matrix[i][0] == 0 || m_matrix[0][j] == 0) {
m_matrix[i][j] = 0;
}
}
if(first_column_has_zero) {
m_matrix[i][0] = 0;
}
}
}
};