0073. Set Matrix Zeroes
https://leetcode.com/problems/set-matrix-zeroes
Description
Given an m x n
integer matrix matrix
, if an element is 0
, set its entire row and column to 0
's, and return the matrix.
You must do it in place.
Example 1:

**Input:** matrix = [[1,1,1],[1,0,1],[1,1,1]]
**Output:** [[1,0,1],[0,0,0],[1,0,1]]
Example 2:

**Input:** matrix = [[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]]
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?
ac
the key is be careful about first row and column
class Solution {
public void setZeroes(int[][] matrix) {
int mR = matrix.length;
int mC = matrix[0].length;
// check first row, first column
boolean setFirstRow = false;
boolean setFirstCol = false;
for (int c = 0; c < mC; c++) {
if (matrix[0][c] == 0) setFirstRow = true;
}
for (int r = 0; r < mR; r++) {
if (matrix[r][0] == 0) setFirstCol = true;
}
// check the rest, mark it first row/col
for (int r = 1; r < mR; r++) {
for (int c = 1; c < mC; c++) {
if (matrix[r][c] == 0) {
matrix[0][c] = 0;
matrix[r][0] = 0;
}
}
}
// set row and col
for (int c = 1; c < mC; c++) {
if (matrix[0][c] == 0) {
for (int r = 0; r < mR; r++) matrix[r][c] = 0;
}
}
for (int r = 1; r < mR; r++) {
if (matrix[r][0] == 0){
for (int c = 0; c < mC; c++) matrix[r][c] = 0;
}
}
// set first row/col
if (setFirstRow) {
for (int c = 0; c < mC; c++) matrix[0][c] = 0;
}
if (setFirstCol) {
for (int r = 0; r < mR; r++) matrix[r][0] = 0;
}
}
}
Last updated
Was this helpful?