73. Set Matrix Zeroes

Description:

https://leetcode.com/problems/set-matrix-zeroes/#/description

Algorithm:

O(m+n) space:

Traverse, record the zero row index and column index.

Set all the zero rows to zero;

Set all the zero columns to zero.

O(1) space:
Use the first row and first column to record whether there is zero in this col/row. (Don’t worry about lost of info, if there is a zero in this row/col, it will be set to zero anyway.)

Code:
1. O(mn)time, O(m+n)space
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
vector<int> zeroRow;
vector<int> zeroColumn;
vector<int> nonzeroRow;
vector<int> nonzeroColumn;

int m = matrix.size();
int n = matrix[0].size();
for (int i = 0; i < m;i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == 0)
{
zeroRow.push_back(i);
zeroColumn.push_back(j);
}
else
{
nonzeroRow.push_back(i);
nonzeroColumn.push_back(j);
}
}
}
zeroRow.erase(unique(zeroRow.begin(), zeroRow.end()), zeroRow.end());
zeroColumn.erase(unique(zeroColumn.begin(), zeroColumn.end()), zeroColumn.end());
for (int i = 0; i < zeroRow.size();i++)
{
matrix[zeroRow[i]] = vector<int>(n, 0);
}
for (int j = 0; j < zeroColumn.size();j++)
{
for (int i = 0; i < m; i++)
matrix[i][zeroColumn[j]] = 0;
}
}
};

2. O(mn) time, O(1)space
class Solution2 {
public:
void setZeroes(vector>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;

bool row_has_zero = false;
bool col_has_zero = false;
for (int i = 0; i < m; i++) if (matrix[i][0] == 0) { col_has_zero = true; break; } for (int j = 0; j < n; j++) if (matrix[0][j] == 0) { row_has_zero = true; break; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } for (int i = 1; i < m;i++) { for (int j = 1; j < n;j++) { if (matrix[0][j] == 0 || matrix[i][0] == 0) matrix[i][j] = 0; } } if (row_has_zero) for (int j = 0; j < n; j++) matrix[0][j] = 0; if (col_has_zero) for (int i = 0; i < m; i++) matrix[i][0] = 0; } };