Skip to content

01.08. Zero Matrix

Description

Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

 

Example 1: 


Input: 

[

  [1,1,1],

  [1,0,1],

  [1,1,1]

]

Output: 

[

  [1,0,1],

  [0,0,0],

  [1,0,1]

]

Example 2: 


Input: 

[

  [0,1,2,0],

  [3,4,5,2],

  [1,3,1,5]

]

Output: 

[

  [0,0,0,0],

  [0,4,5,0],

  [0,3,1,0]

]

Solutions

Solution 1: Array Marking

We use arrays rows and cols to mark the rows and columns to be zeroed.

Then we traverse the matrix again, zeroing the elements corresponding to the rows and columns marked in rows and cols.

The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Here, $m$ and $n$ are the number of rows and columns of the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        rows = [0] * m
        cols = [0] * n
        for i, row in enumerate(matrix):
            for j, v<