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.
1function setZeroes(matrix) {
2 let m = matrix.length;
3 let n = matrix[0].length;
4 let row = new Array(m).fill(false);
5 let col = new Array(n).fill(false);
6
7 for (let i = 0; i < m; i++) {
8 for (let j = 0; j < n; j++) {
9 if (matrix[i][j] === 0) {
10 row[i] = true;
11 col[j] = true;
12 }
13 }
14 }
15
16 for (let i = 0; i < m; i++) {
17 for (let j = 0; j < n; j++) {
18 if (row[i] || col[j]) {
19 matrix[i][j] = 0;
20 }
21 }
22 }
23}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.
1#include <stdio.h>
2#include <stdbool.h>
3
4void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
5 int isCol = 1;
6 int R = matrixSize;
7 int C = *matrixColSize;
8
9 for (int i = 0; i < R; i++) {
10 if (matrix[i][0] == 0) isCol = 0;
11 for (int j = 1; j < C; j++) {
12 if (matrix[i][j] == 0) {
13 matrix[i][0] = 0;
14 matrix[0][j] = 0;
15 }
16 }
17 }
18
19 for (int i = 1; i < R; i++) {
20 for (int j = 1; j < C; j++) {
21 if (matrix[i][0] == 0 || matrix[0][j] == 0) {
22 matrix[i][j] = 0;
23 }
24 }
25 }
26
27 if (matrix[0][0] == 0) {
28 for (int j = 0; j < C; j++) {
29 matrix[0][j] = 0;
30 }
31 }
32
33 if (isCol == 0) {
34 for (int i = 0; i < R; i++) {
35 matrix[i][0] = 0;
36 }
37 }
38}