Question
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
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?
Stats
| Frequency | 5 |
| Difficulty | 3 |
| Adjusted Difficulty | 3 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a very borning question. The O(m+n) space solution is trivial, I will not cover. The constant space solution is making use of 1st row and 1st columns of the input array.
Solution
The idea is clear enough, but writing the code is not as easy. This post is a good explanation and code for the solution.
Difficult point: when there’s 0, set 0; but when there is no 0, do not touch on the value (if original it’s 3, keep it 3).
Code
public void setZeroes(int[][] matrix) {
int m = matrix.length;
if (m == 0) return;
int n = matrix[0].length;
if (n == 0) return;
int firstrow = 1, firstcol = 1;
for (int i = 0; i < m; i ++)
if (matrix[i][0] == 0)
firstcol = 0;
for (int i = 0; i < n; i ++)
if (matrix[0][i] == 0)
firstrow = 0;
for (int i = 1; i < m; i ++) {
for (int j = 1; j < n; j ++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i ++) {
if (matrix[i][0] == 0)
for (int j = 1; j < n; j ++)
matrix[i][j] = 0;
if (firstcol == 0) matrix[i][0] = 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 (firstrow == 0) matrix[0][i] = 0;
}
if(firstrow == 0 || firstcol == 0)
matrix[0][0] = 0;
}