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.
1#include <vector>
2using namespace std;
3
4void setZeroes(vector<vector<int>>& matrix) {
5 int m = matrix.size();
6 int n = matrix[0].size();
7 vector<bool> row(m, false);
8 vector<bool> col(n, false);
9
10 for(int i = 0; i < m; i++) {
11 for(int j = 0; j < n; j++) {
12 if(matrix[i][j] == 0) {
13 row[i] = true;
14 col[j] = true;
15 }
16 }
17 }
18
19 for(int i = 0; i < m; i++) {
20 for(int j = 0; j < n; j++) {
21 if(row[i] || col[j]) {
22 matrix[i][j] = 0;
23 }
24 }
25 }
26}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.
1function setZeroes(matrix) {
2 let m = matrix.length;
3 let n = matrix[0].length;
4 let col0 = 1;
5 for (let i = 0; i < m; i++) {
6 if (matrix[i][0] === 0) col0 = 0;
7 for (let j = 1; j < n; j++) {
8 if (matrix[i][j] === 0) {
9 matrix[i][0] = 0;
10 matrix[0][j] = 0;
11 }
12 }
13 }
14
15 for (let i = 1; i < m; i++) {
16 for (let j = 1; j < n; j++) {
17 if (matrix[i][0] === 0 || matrix[0][j] === 0) {
18 matrix[i][j] = 0;
19 }
20 }
21 }
22
23 if (matrix[0][0] === 0) {
24 for (let j = 0; j < n; j++) {
25 matrix[0][j] = 0;
26 }
27 }
28
29 if (col0 === 0) {
30 for (let i = 0; i < m; i++) {
31 matrix[i][0] = 0;
32 }
33 }
34}