This question is part of NeetCode150 series.
Problem Description
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place.
Solution
APPROACH 1
Space Complexity: O(n+m)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
//we will use these two arrays to track if that particular row/column needs to be marked
int[] rows = new int[n];
int[] columns = new int[m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
rows[i] = 1;
columns[j] = 1;
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(rows[i] == 1 || columns[j] == 1) matrix[i][j] = 0;
}
}
}
}
APPROACH 2
The above approach is not in-place as we used extra space. Instead of maintaining two new arrays to track which rows and columns need to be updated, we can do it using first row and first column. The first cell is an overlap. So, we will use one extra variable for the first row.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
boolean firstRow = false;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(matrix[i][j] == 0){
matrix[0][j] = 0;
if(i == 0){
firstRow = true;
}else{
matrix[i][0] = 0;
}
}
}
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
}
}
//first column
if(matrix[0][0] == 0){
for(int i=0; i<n; i++){
matrix[i][0] = 0;
}
}
//first row
if(firstRow == true){
for(int i=0; i<m; i++){
matrix[0][i] = 0;
}
}
}
}