[LeetCode] 73. Set Matrix Zeroes

Posted on | In

Problem

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

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
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 constant space solution?

Explanation

  1. If we want to use O(mn) space, then we can create a new matrix that is same as the input matrix, then we iterate each element of the input matrix, if we find a zero, then we asign zeros to the new matrix’s corresponding row and column.

  2. If we want to use O(m+n) space, then we create a one dimensional array that has length m to record which row has zero; and create another one dimensional array that has length n to record which column has zero. At the end, we can update the input matrix’s corresponding row to zero and corresponding column to zero.

  3. If we want to use O(1) space, then we cannot create any new array, but we can use the original array’s first row and first column to record each row and each column if they have zero.

    1. First scan the first row or first column, if first row has zero, then mark zeroRow to true; if first column has zero, then mark zeroColumn to true.
    2. Then, we scan from the second row and second column, if the element is zero, then we mark its corresponding first row and first column to zero.
    3. Then, scan again from the second row and second column, if the corresponding first row and first column is zero, then we mark this element to zero.
    4. At the end, if zeroRow is true, then we make the first row to zero. If zeroColumn is true, then we mark the first column to zero.

Solution

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
class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        int numRow = matrix.length;
        int numCol = matrix[0].length;
        
        boolean zeroRow = false;
        boolean zeroCol = false;
        for (int r = 0; r < numRow; r++) {
            if (matrix[r][0] == 0) {
                zeroCol = true;
                break;
            }
        }
        for (int c = 0; c < numCol; c++) {
            if (matrix[0][c] == 0) {
                zeroRow = true;
                break;
            }
        }
        
        for (int r = 1; r < numRow; r++) {
            for (int c = 1; c < numCol; c++) {
                if (matrix[r][c] == 0) {
                    matrix[r][0] = 0;
                    matrix[0][c] = 0;
                }
            }
        }
        
        for (int r = 1; r < numRow; r++) {
            for (int c = 1; c < numCol; c++) {
                if (matrix[0][c] == 0 || matrix[r][0] == 0) {
                    matrix[r][c] = 0;
                }
            }
        }
        
        if (zeroRow) {
            for (int c = 0; c < numCol; c++) {
                matrix[0][c] = 0;
            }
        }
        
        if (zeroCol) {
            for (int r = 0; r < numRow; r++) {
                matrix[r][0] = 0;
            }
        }
    }
}