# Set Matrix Zeroes (C++)

Question : You are given a m x n matrix with integers . if an element is `0`, set its entire row and column to `0`‘s. ( You have to do it in place ) then return the matrix .

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Brute Solution :
We can start iterating the matrix from the first element . Now whenever we hit a zero , we can traverse that row and column and make it zero .
To make it better , we can take two dummy arrays , first dummy arrays will be size of column and one will be size of rows .Say the name of dummy arrays column and row itself.

Now you linearly traverse the matrix , whenever you find a matrix , what you do , you simply set 0 in the coloumn index and simply set 0 in the row index .
Say , in matrix = [[1,1,1],[1,0,1],[1,1,1]] , you hit the first zero at (2,2) , now your dummy arrays will become coloumn[2]=0 and row[2]=0 .
Once you are done doing this , you again linearly traverse the given matrix , once you hit a index , you check its corresponding row and coloumn dummy array . say for (0,0) , you check coloumn[0] and row[0] ,now if any of this is zero , you make matrix[0][0]=0 , similarly for (0,1) you check row[0] and coloumn[1] and change matrix[0][1] , if anyone of it is 0 and so on .Do this for the complete matrix .
Pseudo code :

```
```
int R=matrix.size();
int C=matrix[0].size();
int row[R];
int col[C];

int i, j;

for (i = 0; i < R; i++)
{
row[i] = INT_MAX;
}

for (i = 0; i < C; i++)
{
col[i] = INT_MAX;
}

for (i = 0; i < R; i++)
{
for (j = 0; j < C; j++)
{
if (mat[i][j] == 0)
{
row[i] = 0;
col[j] = 0;
}
}
}

for (i = 0; i < R; i++)
{
for (j = 0; j < C; j++)
{
if ( row[i] == 0 || col[j] == 0 )
{
mat[i][j] = 0;
}
}
}
}``````

Time Complexity : O(nxm + nxm) = O(nxm)
Space Complexity : O(n) + O(m) = O(n)

Optimal Solution :

This is an optimization of previous approach .Instead of taking two dummy arrays explicitly , we will take those two dummy arrays inside the matrix . To do this , we will take first row and coloumn of the matrix as dummy arrays . Here we need two variable , lets say , col and row , which can be initialized with false , i.e. col=fale , and row=false .
Now we will iterate first row and coloumn and check if we have 0 there , if we find 0 in first row then make row=true and if we find 0 in first coloumn , then col=true .
Now we will be traversing , first row to last row , excluding the elements of first coloumn and check if we find 0 somewhere , if so ,we will simply set ,matrix[0][j]=0;
matrix[i][0]=0;

Now start iterating first row to last row , excluding the elements of first coloumn(0th coloum) .If we find , matrix[0][j]==0 or matrix[i][0]==0 we will simply make that element 0 i.e. :
for(int i=1;i<r;i++)
{ for(int j=1;j<c;j++)
{ if(matrix[0][j]==0 or matrix[i][0]==0)
{ matrix[i][j]=0; }
}
}

Finally, using row and col, update first row and first column if needed.

Code :
C++
Function to set matrix zero :

`void setZeroes(vector<vector<int>& matrix) {bool row=false;bool col=false;`

``````    int r=matrix.size();
int c=matrix[0].size();

for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++)
{
if(i==0 and matrix[i][j]==0)
{
row=true;
}
if(j==0 and matrix[i][j]==0)
{
col=true;
}
if(matrix[i][j]==0)
{
matrix[0][j]=0;
matrix[i][0]=0;
}

}
}

for(int i=1;i<r;i++)
{
for(int j=1;j<c;j++)
{
if(matrix[0][j]==0 or matrix[i][0]==0)
{
matrix[i][j]=0;
}
}
}

if(row==true)
{
for(int j=0;j<c;j++)
{
matrix[0][j]=0;
}
}

if(col==true)
{
for(int j=0;j<r;j++)
{
matrix[j][0]=0;
}
}

}``````