# Solution: Set Matrix Zeroes

Let's solve the Set Matrix Zeroes 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:**

- $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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.