Problem description:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example 2:

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?

Solution:

  1. fr = first row, fc = first col
  2. Use first row and first column as markers. If matrix[i][j] = 0, mark respected row and col marker = 0 indicating that later this respective row and col must be marked 0; And because you are altering first row and column, we need to have two variables to track their own status.

  3. For example, if any one of the first row is 0, fr = 0, at the end need to set all first row to 0;

    time complexity: O(mn)
    space complexity: O(1)

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
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row0, col0 = 1, 1
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if not matrix[i][j]:
                    if i == 0: row0 = 0
                    if j == 0: col0 = 0
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        # Notice this starts from 1 because we use first row/col to store
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if not matrix[i][0] or not matrix[0][j]:
                    matrix[i][j] = 0
        if not row0:
            for j in range(len(matrix[0])):
                matrix[0][j] = 0
        if not col0:
            for i in range(len(matrix)):
                matrix[i][0] = 0
```     


```c++
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool fr= false, fc= false;
        for(int i = 0; i< matrix.size(); ++i){
            for(int j= 0; j< matrix[0].size(); ++j){
                if(matrix[i][j] == 0){
                    if(i == 0) fr = true;
                    if(j == 0) fc = true;
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i = 1; i< matrix.size(); ++i){
            for(int j = 1; j< matrix[0].size(); ++j){
                if(matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
        }
        
        if(fc){
            for(int i = 0; i< matrix.size(); ++i)
                matrix[i][0] = 0;
        }
        
        if(fr){
            for(int j = 0; j< matrix[0].size(); ++j)
                matrix[0][j] = 0;
        }
    }
};