Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. I have tried taking the approach where we set row 1 and column 1 as reference rows and columns. I am getting following run-time error on running the code: "ERROR: AddressSanitizer: heap-buffer-overflow on address...."
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int x=1, y=1, col=1,row=1;
int m=matrix.size();
int n=matrix[0].size();
//for 1st row i.e considered as reference row for inner matrix
for(int i=0;i<m;i ){
if(matrix[i][0]==0)
x=0;
}
// for 1st column i.e considered as reference column for inner matrix;
for(int a=0;a<n;a ){
if(matrix[0][a]==0)
y=0;
}
//loop for the inner matrix
for(int i=1;i<m;i ){
for(int j=1;j<n;j ){
if(matrix[i][j]==0){
matrix[0][j]=0;
matrix[i][0]=0;
}
}
}
//for iterating over 1st row of the matrix to check for zeroes.
for(int i=1;i<m;i ){
if(matrix[0][i]==0){
while(i<n){
matrix[i][col]=0;
col ;
};
break;
}
}
//for iterating over 1 column of the matrix to check for zeroes
for(int j=1;j<n;j ){
if(matrix[j][0]==0){
while(j<m){
matrix[row][j]=0;
row ;
};
break;
}
}
if(x==0){
for(int i=0;i<m;i )
matrix[0][i]=0;
}
if(y==0){
for(int j=0;j<n;j )
matrix[j][0]=0;
}
}
};
CodePudding user response：
instead of declaring col and row, use a nested loop in order to iterate over 1st row and 1st column. other than this, there are certain errors in the code. The final code is given below:
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int x=1, y=1;
int m=matrix.size();
int n=matrix[0].size();
//for 1st row i.e considered as pointer row for inner matrix
for(int j=0;j<n;j ){
if(matrix[0][j]==0)
x=0;
}
// for 1st column i.e considered as pointer column for inner matrix;
for(int i=0;i<m;i ){
if(matrix[i][0]==0)
y=0;
}
//loop for the inner matrix
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 iterating over 1st row of the matrix to check for zeroes.
for(int i=1;i<m;i ){
if(matrix[i][0]==0){
for(int j=1;j<n;j )
matrix[i][j]=0;
}
}
//for iterating over 1 column of the matrix to check for zeroes
for(int j=1;j<n;j ){
if(matrix[0][j]==0){
for(int i=1;i<m;i )
matrix[i][j]=0;
}
}
if(x==0){
for(int j=0;j<n;j )
matrix[0][j]=0;
}
if(y==0){
for(int i=0;i<m;i )
matrix[i][0]=0;
}
}
};
CodePudding user response：
Let's check one the last loops in the posted code
void setZeroes(vector<vector<int>>& matrix) {
// ... ^^^^^^^^^^^^^^^^^^^ I assume a row-major representation
int col=1,row=1;
int m = matrix.size();
// ^^^^^^^^^^^^^^^^^ Let's call it the number of rows.
int n = matrix[0].size();
// ^^^^^^^^^^^^^^^^^^^^ That's the number of columns. Let's "hope" that
// the vector isn't empty and that all the rows
// have the same number of columns.
// ...
for(int i=1;i<m;i ){
// ^^^ Note the limit: 'm', which is the number of rows.
if(matrix[0][i]==0){
// ^^^ We are traversing the first row, but if 'n' < 'm'
// that access has undefined behavior.
// Now, I guess you'd want to zero an entire column, but it should
// be the one where the zero in the first row is.
while( i < n ){
// ^^^^^ So, what does 'i' represents now?
matrix[i][col]=0;
// ^^^^^^ are you trying to access a row or a column?
col ;
// 'i' isn't modified, so this loop is either
// infinite or never executed.
};
break; // Why? Why is it here?
}
}
// ...
}
A possible implementation of this algorithm (the one that solves the problem using O(1) additional space) is the following:
#include <algorithm>
#include <vector>
void setZeroes(std::vector<std::vector<int>>& matrix)
{
if ( matrix.empty() ) return;
// Use the first row and column to memorize which column or row to set to zero.
// matrix[0][0] is used for the first row, so we need an extra variable for
// the first column.
bool first_column_has_zero{};
for ( size_t i{}; i < matrix.size(); i )
{
if ( matrix[i][0] == 0 )
first_column_has_zero = true;
for ( size_t j{1}; j < matrix[i].size(); j )
{
if ( matrix[i][j] == 0 )
{
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// Now modify all the rows and columns other than the first ones.
for ( size_t i{1}; i < matrix.size(); i )
{
if ( matrix[i][0] == 0 )
{
std::fill(matrix[i].begin() 1, matrix[i].end(), 0);
}
else
{
for ( size_t j{1}; j < matrix[i].size(); j )
{
if ( matrix[0][j] == 0 )
matrix[i][j] = 0;
}
}
}
// At last, deal with the first row and column.
if ( matrix[0][0] == 0 )
std::fill(matrix[0].begin(), matrix[0].end(), 0);
if ( first_column_has_zero )
for ( size_t i{}; i < matrix.size(); i )
{
matrix[i][0] = 0;
}
}
I actually prefer the one that is O(n m) in space, because it's more straightforward, but your mileage may vary:
#include <algorithm>
#include <vector>
void setZeroes(std::vector<std::vector<int>>& matrix)
{
if ( matrix.empty() ) return;
std::vector<bool> rows(matrix.size());
std::vector<bool> cols(matrix[0].size());
for ( size_t i{}; i < matrix.size(); i )
{
// assert(matrix[i].size() == cols.size());
for ( size_t j{}; j < cols.size(); j )
{
if ( matrix[i][j] == 0 )
{
rows[i] = true;
cols[j] = true;
}
}
}
for ( size_t i{}; i < matrix.size(); i )
{
if ( rows[i] )
{
std::fill(matrix[i].begin(), matrix[i].end(), 0);
}
else
{
std::transform( matrix[i].begin(), matrix[i].end()
, cols.cbegin()
, matrix[i].begin()
, [](auto a, auto b){ return b ? 0 : a; });
}
}
}