Solution: Set Matrix Zeros
Let's solve the Set Matrix Zeros problem using the Matrix Transformations pattern.
Statement
Given a matrix, mat
, if any element within the matrix is zero, set that row and column to zero.
Constraints:
-
mat.row
,mat.col
-
mat[i][j]
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach to solve this problem is by taking an extra matrix, mat2
. First, copy all the elements of the given mat
to mat2
. Then, while traversing mat
, whenever we encounter 0
, we will make the entire row and column of the mat2
to 0
. In the end, again, copy all the elements of mat2
to mat
. This solution has high time and space complexity, which is and , respectively. Let’s see the optimized approach.
Optimized approach using the matrices pattern
The key idea behind this algorithm is to use the matrix’s first row and column as storage space to track which rows and columns need to be zeroed, thus eliminating the need for additional data structures. The corresponding positions in the first row and column are marked when a zero is found. These markers then set the entire row or column to zero in a second pass through the matrix. Using this approach, the algorithm modifies the matrix with minimal extra space required.
Now, let’s look at the workflow of the implementation:
The first step is to get the number of rows and columns of the mat
. Then we set two boolean flags, fcol
and frow
, to indicate any presence of 0
in the first row and first column, respectively, and set both flags to FALSE. Now, we check the first column and first row and set the frow
and fcol
to TRUE if we find any 0
in the first row and the first column, respectively. This is because at this stage, we will not set the entire first row or column to 0
as it can make the following rows and columns 0
.
Now, we check all the elements row-wise (by ignoring the first row and first column), and if a 0
is found, we set the first element in that row and column to 0
. Now, we set 0
in rows and columns where required by following rules:
- Check every row’s first element, starting from the second row, and if it is
0
, set all values in that row to0
. - Check every column’s first element, starting from the second column, and if it is
0
, set all values in that row to0
.
Now, we check the first row and first column. If the values of frow
and fcol
are TRUE, it indicates any 0
in the first row and first column, respectively. We will set 0
in the corresponding row and column.
In the end, we return the mat
.
Let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.