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)$