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.
1public class Solution {
2 public void SetZeroes(int[][] matrix) {
3 int m = matrix.Length;
4 int n = matrix[0].Length;
5 bool[] row = new bool[m];
6 bool[] col = new bool[n];
7
8 for (int i = 0; i < m; i++) {
9 for (int j = 0; j < n; j++) {
10 if (matrix[i][j] == 0) {
11 row[i] = true;
12 col[j] = true;
13 }
14 }
15 }
16
17 for (int i = 0; i < m; i++) {
18 for (int j = 0; j < n; j++) {
19 if (row[i] || col[j]) {
20 matrix[i][j] = 0;
21 }
22 }
23 }
24 }
25}This 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.
1def setZeroes(matrix):
2 m, n = len(matrix), len(matrix[0])
3 col0 = 1
4 for i in range(m):
5 if matrix[i][0] == 0:
6 col0 = 0
7 for j in range(1, n):
8 if matrix[i][j] == 0:
9 matrix[i][0] = 0
10 matrix[0][j] = 0
11
12 for i in range(1, m):
13 for j in range(1, n):
14 if matrix[i][0] == 0 or matrix[0][j] == 0:
15 matrix[i][j] = 0
16
17 if matrix[0][0] == 0:
18 for j in range(n):
19 matrix[0][j] = 0
20
21 if col0 == 0:
22 for i in range(m):
23 matrix[i][0] = 0