73. Set Matrix Zeroes
Given an m x n
integer matrix matrix
, if an element is 0
, set its entire row and column to 0
's.
You must do it in place.
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Follow up:
- A straightforward 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:
class Solution {
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
Set<Integer> rows = new HashSet<Integer>();
Set<Integer> cols = new HashSet<Integer>();
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (matrix[i][j] == 0){
rows.add(i);
cols.add(j);
}
}
}
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (rows.contains(i) || cols.contains(j)){
matrix[i][j] = 0;
}
}
}
}
}
// TC:O(m*n)
// SC:O(m+n)