Reference: LeetCode
Difficulty: Medium

My Post: Java Solutions Extra Space + No Extra Space

Problem

Given a m x n matrix, if an element is 0s, set its entire row and column to 0. Do it in-place.

Example:

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
Input: 
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

Follow up:

  • A straight forward solution using O(mn) space is probably a bad idea.
  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a O(1) space solution?

Analysis

Extra Space

Use two sets rows and cols to record which row and column should be set to zeroes.

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
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
Set<Integer> rows = new HashSet<>(); // rows that have zero
Set<Integer> cols = new HashSet<>();
// calculate zero-rows and columns
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
// set zeroes
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (rows.contains(i) || cols.contains(j)) {
matrix[i][j] = 0;
}
}
}
}

Time: $O(MN)$
Space: $O(M + N)$

Brute-Force + O(1) Space

We need two passes. The first pass is to set relevant non-zeroes to MODIFIED. The second pass is to set MODIFIED to 0.

Note: This value should not be in the matrix already; otherwise, this method won’t work.

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
private final static int MODIFIED = -1000000;

public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
// set non-zeroes as MODIFIED
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) { // set zeroes
for (int k = 0; k < m; ++k) { // column
if (matrix[k][j] != 0) matrix[k][j] = MODIFIED;
}
for (int k = 0; k < n; ++k) { // row
if (matrix[i][k] != 0) matrix[i][k] = MODIFIED;
}
}
}
}
// restore
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == MODIFIED) matrix[i][j] = 0;
}
}
}

Time: $O(MN \times (M + N))$
Space: $O(1)$

Bette + O(1) Space

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
int m = matrix.length;
int n = matrix[0].length;
boolean isFirstRowZero = false;
boolean isFirstColZero = false;

// see if we need to set first row and column later
if (matrix[0][0] == 0) {
isFirstRowZero = true;
isFirstColZero = true;
} else {
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
isFirstColZero = true;
break;
}
}
for (int j = 0; j < n; ++j) {
if (matrix[0][j] == 0) {
isFirstRowZero = true;
break;
}
}
}
// set the first cell of each row or column as zero if necessary
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) { // set zeroes
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// set rows as zeroes
for (int i = 1; i < m; ++i) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; ++j) {
matrix[i][j] = 0;
}
}
}
// set colums as zeroes
for (int j = 1; j < n; ++j) {
if (matrix[0][j] == 0) {
for (int i = 1; i < m; ++i) {
matrix[i][j] = 0;
}
}
}
// set the first row and first column
if (isFirstColZero) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}

if (isFirstRowZero) {
for (int j = 0; j < n; ++j) {
matrix[0][j] = 0;
}
}
}

Time: $O(MN)$
Space: $O(1)$


Comment