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.
1#include <stdio.h>
2#include <stdbool.h>
3
4void setZeroes(int** matrix, int matrixSize, int* matrixColSize){
5 bool row[matrixSize];
6 bool col[*matrixColSize];
7
8 for(int i = 0; i < matrixSize; ++i) row[i] = false;
9 for(int i = 0; i < *matrixColSize; ++i) col[i] = false;
10
11 for (int i = 0; i < matrixSize; ++i) {
12 for (int j = 0; j < *matrixColSize; ++j) {
13 if (matrix[i][j] == 0) {
14 row[i] = true;
15 col[j] = true;
16 }
17 }
18 }
19
20 for (int i = 0; i < matrixSize; ++i) {
21 for (int j = 0; j < *matrixColSize; ++j) {
22 if (row[i] || col[j]) {
23 matrix[i][j] = 0;
24 }
25 }
26 }
27}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#