Solution: Set Matrix Zeroes

Statement

Given a matrix, mat, if any element within the matrix is zero, set that row and column to zero.

Constraints:

• $1 \le$ mat.row, mat.col $\le 20$
• $-2^{31} \le$ mat[i][j] $\le 2^{31}$

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 $O((mn) \times (m+n))$ and $O(mn)$, 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 to 0.
• Check every column’s first element, starting from the second column, and if it is 0, set all values in that row to 0.

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: