Problem:
Given a matrix , if any of its element is zero , make all the elements in both the row and column of the element to zero.
For example:
For the given matrix:
[[1,1,1],[1,0,1],[1,1,1]]
The second row second column has the value zero.
So make all the values in the second row and second column as zero.
The output is:
[[1,0,1],[1,0,1],[1,0,1]]
Constraints:
You should not use any additional memory in proportion to the input.
That is you should solve this problem in place.
Space complexity should be O(1)
Try out the solution here:
https://leetcode.com/problems/set-matrix-zeroes/
Solution:
Approach 1: Use additional memory
If you can use additional memory , the solution is simple.
Iterate through all the elements in the matrix and collect all the rows and columns which have a value zero separately.
Iterate through the elements in the matrix again and for whichever rows or columns we had collected earlier make the element in that row and column as zero.
Here is the code:
class Solution {
public void setZeroes(int[][] matrix) {
int noOfRows = matrix.length;
int noOfCols = matrix[0].length;
boolean[] rows = new boolean[noOfRows];
boolean[] columns = new boolean[noOfCols];
for(int i=0;i<noOfRows;i++){
for(int j=0;j<noOfCols;j++){
if(matrix[i][j]==0){
rows[i] = true;
columns[j]=true;
}
}
}
for(int i=0;i<noOfRows;i++){
for(int j=0;j<noOfCols;j++){
if(rows[i] ==true || columns[j] == true){
matrix[i][j] = 0;
}
}
}
}
}
Approach 2: Without additional memory (In place)
In this case instead of storing the values in additional memory , you can use the matrix itself to store the information whether the rows and columns should be filled with zeroes or not.
We can use the first row and first column to store these information.
If the second column has to be filled with zeroes , then you can mark the first row second column value to be 0.
If the third column has to be filled with zeroes , then you can mark the first row third column value to be 0.
So if any column values need to be filled with zero , we will fill the corresponding column value in first row as zero.
Similarly if we want any row to be filled with zeroes , then we will fill the corresponding row in the first column to be zero.
So the first row and first column of the matrix will serve as the information store for processing the remaining rows and columns.
Now there is one difficulty here.
How do we know whether the first row need to be filled with zeroes or not?
How do we know whether the first column need to be filled with zeroes or not?
Since we are using them as a datastore we need to deal with them separately.
We can use the first row first column (matrix[0][0]) to store one of these info.
Let’s use it to store the info of whether to fill the first row with zeroes (if any of the element in the first row is zero)
Let’s use another additional variable to store the info of whether to fill the first column with zeroes (if any of the element in the first column is zero)
ALGORITHM:
STEP 1: Find if any of the element in the first column is zero. If so set a boolean variable to true.
STEP 2: Find if any of the element in the first row is zero. If so set the first row first column (index 0) to 0.
STEP 3: Iterate through the matrix from first row first column:
STEP 3a: If any of the elements is zero , set the corresponding row first column value to 0 and the corresponding column first row value to 0.
STEP 4: Iterate through the array again and set the value zero to the elements whose corresponding row first column value is zero or whose corresponding column first row value is zero.
STEP 5: If the boolean variable set in STEP 1 is true fill all first column values to zero.
STEP 6: If the first row first column value calculated in STEP 2 is zero , fill the entire first row with zeroes.
Code:
class Solution {
public void setZeroes(int[][] matrix) {
int noOfRows = matrix.length;
int noOfCols = matrix[0].length;
boolean firstColumnZero = false;
for(int j=0;j<noOfRows;j++){
if(matrix[j][0] ==0){
firstColumnZero = true;
}
}
//find if first row needs to be replaced by zeroes
//use matrix[0][0] to store that value
for(int i=0;i<noOfCols;i++){
if(matrix[0][i] ==0){
matrix[0][0] =0;
}
}
for(int i=1;i<noOfRows;i++){
for(int j=1;j<noOfCols;j++){
if(matrix[i][j]==0){
matrix[i][0]=0;
matrix[0][j]=0;
}
}
}
for(int i=1;i<noOfRows;i++){
for(int j=1;j<noOfCols;j++){
if(matrix[i][0]==0 ||matrix[0][j]==0 ){
matrix[i][j]=0;
}
}
}
if(matrix[0][0] ==0){
for(int i=0;i<noOfCols;i++){
matrix[0][i] =0;
}
}
if(firstColumnZero){
for(int j=0;j<noOfRows;j++){
matrix[j][0] = 0;
}
}
}
}
Time complexity :
O(m) for finding if the first column needs to be filled with zero where m is the number of rows
O(n) for finding if the first row needs to be filled with zero where n is the number of columns
O(m*n) for setting the first row and first column values to zero based on the corresponding column and row elements .
O(m*n) again for filling the rows and columns with zero wherever they need to be.
O(m) again for filling the first column with zeroes if required.
O(n) again for filling the first row with zeroes if required.
In total , the time complexity is O(m*n)
Space complexity is O(1) since we are solving the problem in place.
That’s it!
Leave a Reply