Problem Description
Link to Question: https://leetcode.com/problems/set-matrix-zeroes/description/
Given an n x m integer matrix matrix, if an element is 0, set its entire row and column to 0's.
Using a New Matrix
- Create a new matrix → new_matrix.
- Traverse the
matrix, whenever a 0 is encountered, set the corresponding row and column in thenew_matrixto be zero.
Code
#include <bits/stdc++.h>
void set_zero(vector<vector<int>>& matrix, int row, int col)
{
int n=matrix.size();
int m=matrix[0].size();
for(int i=0; i<n; i++)
matrix[i][col] = 0;
for(int j=0; j<m; j++)
matrix[row][j] = 0;
}
void setZeros(vector<vector<int>> &matrix)
{
//Create a new matrix
auto v = matrix;
int n=matrix.size(); //# rows
int m=matrix[0].size(); //# cols
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(matrix[i][j]==0)
{
set_zero(v, i, j);
}
}
}
matrix = v;
}
Complexity Analysis
- Time: , where m+n is the time required to turn corresponding row, and column to 0.
- Space:
used by
new_matrix
Space Improved Solution
We can improve the space, if we just mark the corresponding row and column that needs to be turn into 0s while traversing the matrix. Let’s do that:
- Inititialise two flag arrays,
row_flag[#rows], andcol_flag[#cols]-
row_flag[i]andcol_flag[i]can take either of two values, -1 or 0. - ‘-1’ means keep this row or col as it is.
- ‘0’ means turn this row or col into 0.
-
- Traverse the
matrix. On encountering a 0, mark the corresponding flags. - Now using our flag arrays, make the required cells of the matrix to be ‘0’.
Code
#include <bits/stdc++.h>
void setZeros(vector<vector<int>> &matrix)
{
int n=matrix.size();
int m=matrix[0].size();
vector<int> row_flag(n, -1);
vector<int> col_flag(m, -1);
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(matrix[i][j]==0)
{
//mark the row and column
row_flag[i]=0;
col_flag[j]=0;
}
}
}
//Change the cells of matrix using
//flag arrays
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
//Change to '0' if any of the row or col
//was marked
if(row_flag[i] == 0 || col_flag[j] == 0)
matrix[i][j]=0;
}
}
}
Complexity Analysis
- Time:
- Space: used by flag arrays.
Optimal Solution
We want to get rid of the space used by our flag arrays. How about using the 0th row and 0th column as flag arrays for marking purposes?
It turns out we can! We need to take care of one little caveat. Since the cell matrix[0][0] can represent two states only (0 and non-zero), so, it can be either part of the col_flag or row_flag. Let’s say. We make it the part of row_flag to mark the 0th row. Then, we require one more variable to handle marking the 0th column. The image makes it more clear.
Here’s the Approach then,
- Traverse the
matrix, and mark rows and columns which has to be turned 0. - Traverse the
matrix[1,1] → [n,m] i.e except first row and first column, and turn a cell 0 if either one of its row or column is marked. - [IMPORTANT] We will modify the 0th row before the 0th column. The reason is, there’s a chance that matrix[0][0] is changed from a non-zero value to zero by the independent variable
is_col0! This will be falsely signify that first row also needs to be turned into zeros!
Code
void setZeros(vector<vector<int>> &matrix)
{
int n = matrix.size();
int m = matrix[0].size();
bool is_col0 = false; // Marker for 0th colum
//Mark the Rows and Columns
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if (matrix[i][j] == 0) {
// Mark ith row
matrix[i][0] = 0;
// Mark jth column with care!
if (j != 0) // any other column than 0th
matrix[0][j] = 0;
else
is_col0 = true;
}
}
}
//Change the matrix from [1,1]=>[n-1,m-1]
for(int i=1; i<n; i++)
{
for(int j=1; j<m; j++)
{
if(matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
//Change 0th row first,
//matrix[0][0] is 0th row's flag
if(matrix[0][0] == 0)
for(int j=0; j<m; j++)
matrix[0][j] = 0;
//Change 0th column
if(is_col0)
for(int i=0; i<n; i++)
matrix[i][0]=0;
}
Complexity Analysis
- Time:
- Space: Finally 🥺!
Top comments (0)