Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
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?
Analysis
Using $O(mn)$ and $O(m + n)$ space to implement it is easy. Just check the zeros and save their positions.
Since we need to do it in place, we can take full advantage of the matrix to save the useful information. We can use the first row and the first column to save whether there is a zero in such row or column. But we need to be careful that it’s possible that there is no zero in the first row or first column. When you change some entry in the first row to zero, you may not be able to know whether there is zero in this row or not. So we need to check it first.
And then we can check other entry. If it’s zero, for example, if matrix[i][j] is zero, we can update matrix[i][0] and matrix[0][j] to zero. After checking all entries, we can update the matrix according the the first row and the first column. If there is a zero, it means that we need to update all row or all column to zero.
Finally, we need to update the first row or first column. What we need is the checking information we mentioned above. According to them, we can decide it’s correct or not to update the first row or first column.
Code
|
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 |
public class Solution { public void setZeroes(int[][] matrix) { boolean firstRowZero = false; boolean firstColumnZero = false; int m = matrix.length; int n = matrix[0].length; for (int i = 0; i < m; i++) { if (matrix[i][0] == 0) { firstColumnZero = true; break; } } for (int i = 0; i < n; i++) { if (matrix[0][i] == 0) { firstRowZero = true; break; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[0][j] = 0; matrix[i][0] = 0; } } } for (int i = 1; i < m; i++) { if (matrix[i][0] == 0) { for (int j = 1; j < n; j++) matrix[i][j] = 0; } } for (int i = 1; i < n; i++) { if (matrix[0][i] == 0) { for (int j = 1; j < m; j++) matrix[j][i] = 0; } } if (firstRowZero) { for (int i = 0; i < n; i++) matrix[0][i] = 0; } if (firstColumnZero) { for (int i = 0; i < m; i++) matrix[i][0] = 0; } } } |
Complexity
The time complexity is $O(mn)$. But the space complexity is constant.