/
0073_Set_Matrix_Zeroes.py
43 lines (40 loc) · 1.53 KB
/
0073_Set_Matrix_Zeroes.py
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# O(1) space:
# 1. check and store whether row 0 and col 0 has zero (time O(m + n))
# 2. go over, if found matrix[i][j] == 0, set matrix[i][0], matrix[0][j] = 0, O(mn)
# 3. go over rows and cols start from index 1,
# if row or col head == 0, set entire row/col = 0, O(mn)
# 4. if row 0 and col 0 has zero in step1., set those to 0, O(m + n)
row0 = col0 = False
for c in range(len(matrix[0])):
if matrix[0][c] == 0:
row0 = True
break
for r in range(len(matrix)):
if matrix[r][0] == 0:
col0 = True
break
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for c in range(1, len(matrix[0])):
if matrix[0][c] == 0:
for r in range(1, len(matrix)):
matrix[r][c] = 0
for r in range(1, len(matrix)):
if matrix[r][0] == 0:
for c in range(1, len(matrix[0])):
matrix[r][c] = 0
if row0:
for c in range(len(matrix[0])):
matrix[0][c] = 0
if col0:
for r in range(len(matrix)):
matrix[r][0] = 0
return