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.
1import java.util.*;
2
3public class MatrixZero {
4 public void setZeroes(int[][] matrix) {
5 int m = matrix.length;
6 int n = matrix[0].length;
7 boolean[] row = new boolean[m];
8 boolean[] col = new boolean[n];
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 }
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 public void SetZeroes(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;
bool isCol = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) isCol = true;
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (matrix[0][0] == 0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}