DSA
Set Matrix Zeros
Covers: Set, Greedy. Optimal — Time O(m*n), Space O(1).
Practice here
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
Set Approach#
-
Intuition: You cannot zero out rows and columns on the fly during the scan — doing so would introduce new zeros and cause false propagation. Instead, first record which rows and columns must be zeroed, then apply the changes in a separate pass.
-
Mechanics: One full scan collects the indices of rows and columns that contain at least one zero into two sets. A second pass iterates over those sets and zeros out the corresponding entire rows and columns in the original matrix.
-
Trade-off: Two clean O(m×n) passes with easy-to-read logic. The sets use O(m+n) auxiliary space, which the Greedy approach below eliminates by repurposing the matrix's own first row and column as markers.
-
Splitting it into two passes:
- Mark first
- Clear later
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
set<int> rows, cols;
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<matrix[0].size();j++)
{
if(matrix[i][j]==0)
{
rows.insert(i);
cols.insert(j);
}
}
}
// set rows zero
for(int row: rows)
{
cout<<"setting row: "<<row<<endl;
for(int j=0;j<matrix[0].size();j++)
matrix[row][j] = 0;
}
// set cols zero
for(int col: cols)
{
cout<<"setting col: "<<col<<endl;
for(int j=0;j<matrix.size();j++)
matrix[j][col] = 0;
}
}
};
Time Complexity: O(m*n)
Space Complexity: O(m+n)
Greedy Approach#
Intuition: Instead of allocating extra sets, repurpose the matrix's own first row and first column as marker flags — achieving O(1) auxiliary space.
The catch: the first row and column might themselves contain original zeros, which we'd accidentally overwrite when using them as markers. So we save that state upfront with two booleans.
Four-phase algorithm:
- Save — check if the first column or first row originally has any zero (store in firstColZero / firstRowZero).
- Mark — scan the inner submatrix (rows 1..m−1, cols 1..n−1). For each zero at (i, j), set matrix[0][j] = 0 and matrix[i][0] = 0 to flag that column and row.
- Apply — scan the inner submatrix again. Zero out matrix[i][j] if its column marker matrix[0][j] or row marker matrix[i][0] is 0.
- Restore — use the saved booleans to zero out the actual first row/column if they originally contained a zero.
By handling the first row/column last, we avoid corrupting the markers before we've finished reading them.
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool firstColZero = false;
bool firstRowZero = false;
for(int i=0;i<m;i++){
if(matrix[i][0] == 0){
firstRowZero = true;
break;
}
}
for(int j=0;j<n;j++){
if(matrix[0][j] == 0){
firstColZero = true;
break;
}
}
// mark first row/col as zero
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
if(matrix[i][j]==0){
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
//handle all zeros referencing first row/col
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(firstRowZero){
for(int i=0;i<m;i++){
matrix[i][0] = 0;
}
}
if(firstColZero){
for(int j=0;j<n;j++){
matrix[0][j] = 0;
}
}
}
};
Time Complexity: O(m*n)
Space Complexity: O(1)