73. Set Matrix Zeroes

2019-05-23

73. Set Matrix Zeroes

Given a _m_ x _n_ matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output:
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
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]
]

Follow up:

  • A straight forward solution using O(_mn_) space is probably a bad idea.
  • A simple improvement uses O(_m_ + _n_) space, but still not the best solution.
  • Could you devise a constant space solution?

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    # @param matrix, a list of lists of integers
    # RETURN NOTHING, MODIFY matrix IN PLACE.
    def setZeroes(self, matrix):
        first_row = 1
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    if i == 0:
                        first_row = 0
                        continue
                    else:
                        matrix[i][0] = 0
                        matrix[0][j] = 0
                        continue

        for i in range(1,len(matrix)):
            if matrix[i][0] == 0:
                matrix[i] = [0] * len(matrix[0])

        for j in range(0,len(matrix[0])):
            if matrix[0][j] == 0:
                for idx in range(1,len(matrix)):
                    matrix[idx][j] = 0

        if first_row == 0:
            matrix[0] = [0] * len(matrix[0])

        return
-->