Set Matrix Zeroes
Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do not return anything, modify the matrix in-place.
Constraints:
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Examples:
Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
Explanation: The first row and the second column are set to 0 because of the 0 at matrix[1][1].
Solutions
Using Extra Space
This solution uses two sets to keep track of the rows and columns that need to be set to 0. It first iterates over the matrix to find the rows and columns that contain a 0, and then it iterates over the matrix again to set the corresponding elements to 0.
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Set<Integer> rows = new HashSet<>();
Set<Integer> cols = new HashSet<>();
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);
}
}
}
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;
}
}
}
}In-Place
This solution uses the first row and column of the matrix to keep track of the rows and columns that need to be set to 0. It first iterates over the matrix to find the rows and columns that contain a 0, and then it iterates over the matrix again to set the corresponding elements to 0.
const setZeroes = (matrix) => {
const m = matrix.length;
const n = matrix[0].length;
let isCol = false;
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) isCol = true;
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
if (matrix[0][0] === 0) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (isCol) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
};
Follow-up:
How would you solve this problem if you were not allowed to use any extra space?
