class Solution {
public:
void setMatrixZeroes(vector<vector<int>> &mat) {
int n = mat.size();
int m = mat[0].size();
bool firstRowHasZero = false;
bool firstColHasZero = false;
// Check if the first row has any zero
for (int j = 0; j < m; j++) {
if (mat[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// Check if the first column has any zero
for (int i = 0; i < n; i++) {
if (mat[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// Use the first row and column to mark zeros
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (mat[i][j] == 0) {
mat[i][0] = 0;
mat[0][j] = 0;
}
}
}
// Update the matrix based on the markers
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (mat[i][0] == 0 || mat[0][j] == 0) {
mat[i][j] = 0;
}
}
}
// Update the first row if needed
if (firstRowHasZero) {
for (int j = 0; j < m; j++) {
mat[0][j] = 0;
}
}
// Update the first column if needed
if (firstColHasZero) {
for (int i = 0; i < n; i++) {
mat[i][0] = 0;
}
}
}
};
The idea here is using the first row and column as a Dynamic Programming table to mark which rows and columns need to be zeroed out.
That being done, then first column and row itself is updated at the end.