Sponsored
Sponsored
This approach uses two additional arrays to track the rows and columns that need to be zeroed.
- Traverse the matrix and mark rows and columns that need to be zeroed.
- Then, update the matrix based on the values in these arrays.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m + n) for the additional arrays.
1def setZeroes(matrix):
2 m, n = len(matrix), len(matrix[0])
3 row = [False] * m
4 col = [False] * n
5
6 for i in range(m):
7 for j in range(n):
8 if matrix[i][j] == 0:
9 row[i] = True
10 col[j] = True
11
12 for i in range(m):
13 for j in range(n):
14 if row[i] or col[j]:
15 matrix[i][j] = 0This approach uses the matrix itself to track zeroes.
- Use the first row and column as markers.
- Traverse the matrix and if an element is zero, mark its row and column.
- Traverse again and set matrix elements to zero based on marked rows and columns.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(1) since the algorithm runs in constant space.
1