Leetcode: Set Matrix Zeroes
This question is asked on Oracle and Facebook. It is as follows:
Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place. We want to figure out a constant space solution. If not, we can get a simple improvement using O(m + n) space.
Here are some examples:
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]]
It's easy to code the brute force solution, by storing an ArrayList of the row and column and iterate it twice, but you want to do it without any extra space or constant extra space at the maximum. Linear Memory doesn't work either.
For every column, we check if it contains a 0 and we check for every row if it contains a zero. The memory complexity is now height + width, which isn't too bad so far. :) which is O(H + W), which we want to improve.
class Solution {
public:
void setZeroes(vector<vector<int>>&matrix) {
const int H = matrix.size();
const int W = matrix[0].size();
vector<bool> row_zero(H);
vector<bool> column_zero(W);
for(int row = 0; row < H; ++row) {
for(int col = 0; col < W; ++col) {
if(matrix[row][col] == 0) {
row_zero[row] = true;
column_zero[col] = true;
}
}
}
for(int row = 0; row < H; ++row) {
for(int col = 0; col < W; ++col) {
if(row_zero[row] || column_zero[col]) {
matrix[row][col] = 0;
}
}
}
}
};
This is incorrect. New cells containing zeros are not the same as initial zeroes, remember that.
Why don't we go for a matrix row by row? Why don't we assign boolean values from rows up to N? We move row by row and create a single variable figuring out whether there's a zero there. We should know whether every column contains zero, and then for every row, we can see whether a row contains zero and mark anything that contains zero. The following code reduces the memory complexity to O( hW).
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
const int W = matrix.size();
const int W = matrix[0].size();
vector<bool> column_zero(W);
for(int row = 0; row < H; ++row) {
for(int col = 0; col < W; ++col) {
if(matrix[row][col] == 0) {
column_zero[col] = true;
}
}
}
for(int row = 0; row < H; ++row) {
bool contains_zero = false;
for(int col = 0; col < W; ++col) {
if(matrix[row][col] == 0) {
contains_zero = true;
break;
}
}
for(int col = 0; col < W; ++col) {
if(contains_zero || column_zero[col]) {
matrix[row][col] = 0;
}
}
}
}
};
This is basically the first method, refactored to take less space but the same amount of time efficiency. Now we have reduced the memory complexity to O(W) and now we should try to figure out how to get extra memory, so how to do it? We can do the first row, and for every point, we look at the first row to see if something contains a zero, but the first row will not be marked correct. We use the first row to contain the information where columns should be set as zero, and the first column to obtain the information where the rows should be set as zero. I believe afterward, we change the respective row and column and set the zeros accordingly. Here's the final implementation:
class Solution {
public:
void setZeroes(vector<vector<int>>&matrix) {
const int H = matrix.size();
const int W = matrix[0].size();
bool first_row_zero = false;
//determines if the first row is 0. We fix this at the end of the program.
for(int col = 0; col < W; ++col) {
if(matrix[0][col] == 0){
first_row_zero = true;
break;
}
}
//if an element equals to zero, we can go ahead and set that column equal to zero as well.
for(int row = 0; row < H; ++row) {
for(int col = 0; col < W; ++col) {
if(matrix[row][col] == 0) {
matrix[0][col] = 0;
}
}
}
for(int row = 1; row < H; ++row) {
//see if a row contains zero and fill it if it does.
bool contains_zero = false;
for(int col = 0; col < W; ++col) {
if(matrix[row][col] == 0) {
contains_zero = true;
break;
}
}
for(int col = 0; col < W; ++col) {
if(contains_zero || matrix[0][col] == 0) {
matrix[row][col] = 0;
}
}
}
//set all the columns in the first row equal to zero now.
if(first_row_zero) {
for(int col = 0; col < W; ++col) {
matrix[0][col] = 0;
}
}
}
};
So to summarize:
1. Determine if there Is a zero in the first row.
2. Set the column of the first row of an element equal to 0 if an alternate row with the same column equals to zero.
3. See if a row contains zero, and fill it if it does.
4. Set all the columns in the first row equal to zero now, if it so requires.
The moral of the story, to do in place, basically use the same memory as storage, and figure out a way to keep what is needed to complete the problem.
Comments
Post a Comment