0, its entire row and column are set to 0.
Problem
You are given anm × n integer matrix. If an element in the matrix is 0, set its entire row and column to 0.
The modification must be done in-place.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
matrix = [ [1,1,1], [1,0,1], [1,1,1] ]Output
[ [1,0,1], [0,0,0], [1,0,1] ]matrix[1][1] is 0, its entire row and column are set to 0.
Solution
This problem can be solved using the first row and first column as markers, allowing us to achieveO(1) extra space.
The main challenge is that if we immediately set a row or column to
0 while scanning the matrix, we may create new zeroes that were not present in the original matrix. Those newly created zeroes could incorrectly cause additional rows and columns to be set to zero.
Instead, we use the first row and first column to record which rows and columns originally contained a zero.
For every zero at
matrix[i][j], we mark its row using matrix[i][0] = 0 and its column using matrix[0][j] = 0.
Because the first row and first column are being used as markers, we separately remember whether they originally contained a zero.
After marking, we traverse the inner part of the matrix and set a cell to zero if its corresponding row or column has been marked.
Finally, we process the first row and first column themselves.
class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
boolean firstRowZero = false;
boolean firstColumnZero = false;
// Check if the first row contains a zero.
for (int j = 0; j < m; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}
// Check if the first column contains a zero.
for (int i = 0; i < n; i++) {
if (matrix[i][0] == 0) {
firstColumnZero = true;
break;
}
}
// Use the first row and column as markers.
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Set marked rows to zero.
for (int i = 1; i < n; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < m; j++) {
matrix[i][j] = 0;
}
}
}
// Set marked columns to zero.
for (int j = 1; j < m; j++) {
if (matrix[0][j] == 0) {
for (int i = 1; i < n; i++) {
matrix[i][j] = 0;
}
}
}
// Set the first row to zero if needed.
if (firstRowZero) {
for (int j = 0; j < m; j++) {
matrix[0][j] = 0;
}
}
// Set the first column to zero if needed.
if (firstColumnZero) {
for (int i = 0; i < n; i++) {
matrix[i][0] = 0;
}
}
}
}
Complexity
The matrix is traversed a constant number of times, resulting inO(n × m) time complexity, and only a constant number of variables is used apart from the matrix itself, resulting in O(1) extra space.