Solution: Set Matrix Zeros

Let's solve the Set Matrix Zeros problem using the Matrix Transformations pattern.

We'll cover the following

Statement
Solution
- Naive approach
- Optimized approach using the matrices 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 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:

def set_matrix_zeros(mat):
    rows = len(mat)
    cols = len(mat[0])
    fcol = False
    frow = False
    for i in range(rows):
        if mat[i][0] == 0:
            fcol = True
    for i in range(cols):
        if mat[0][i] == 0:
            frow = True
    for i in range(1, rows):
        for j in range(1, cols):
            if mat[i][j] == 0:
                mat[0][j] = mat[i][0] = 0
    for i in range(1, rows):
        if mat[i][0] == 0:
            for j in range(1, cols):
                mat[i][j] = 0
    for j in range(1, cols):
        if mat[0][j] == 0:
            for i in range(1, rows):
                mat[i][j] = 0
    if fcol:
        for i in range(rows):

Enter to Rename, Shift+Enter to Preview

Set Matrix Zeros

Solution summary#

Calculate the number of rows and columns of the mat.
Set fcol and frow to FALSE.
Check the first column and first row. If any element from the first row or first column is 0, set frow or fcol to TRUE, respectively.
Check all the elements row-wise by ignoring the first row and first column. If a 0 is found, we set the first element in that row and column to 0.
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’s 0, set all values in that row to 0.
If frow is TRUE, set 0 in the first row.
If fcol is TRUE, set 0 in the first column.
Return mat.

Time complexity#

The time complexity of this algorithm is $O(m \times n)$ , where $m$ and $n$ are the dimensions of the matrix.

Space complexity#

The space complexity is $O(1)$ because we use no extra memory.

Set Matrix Zeros

Rotate Image