CareerCup

Here is my answer to this question. The question is not clear. Are we just check one element in the Matrix? Do we need to check multiple ones?

basicalgos.blogspot.com/2012/03/given-matrix-of-0s-nd-1s.html

Assuming the matrix is int[m,n] a, you just need to check the elements in submatrix [1,1] to [m-2,n-2]. If a[i,j] is 0, then you set the edge of its col and row be 0. In this case a[0,j],a[m-1,j],a[i,0],a[i,n-1] be zero. After checking all elements then check the edge of the matrix, if a[i,0] and a[i,n-1] are both 0 then set all elements in row i be 0. Similarly if a[0,j] and a[m-1,j] are 0 then set all element in col j be 0.
Before all this. You need 4 variables to record if elements in specific edge should be set to 0.
Ex:
1011
1111
1101
1111

First you need 4 variables, bool left=false,right=false,top=true (because a[0,1] is 0), bottom=false. Also set a[3,1] be 0 because a[0,1] is 0:

1011
1111
1101
1011

Then check sub-matrix from a[1,1] to a[3,3], finding a[2,2] is 0. So set a[0,2],a[3,2],a[2,0],a[3,0] be 0:

1001
1111
0100
1001

Now check the edges again and reset all cols and rows with edge be 0:

1001
1001
0000
1001

Finally check 4 variables again and reset edges:

0000
1001
0000
1001

Time: O(MN)
Space:O(1)

#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
int main()
{
int a=3;
int b=3;
int matrix[3][3]={ {1,0,1},{1,0,1},{1,1,1}};
int row[a];
int col[b];
for(int i=0;i<a;i++) {
for(int j=0;j<b;j++)
{ if( matrix[i][j]==0)
{
row[i]=1;
col[j]=1;
}
}
}
for(int i=0;i<a;i++) {
for(int j=0;j<b;j++)
{if((row[i]==1) || (col[j]==1))
{
matrix[i][j]=0;
}
}
}
for(int i=0;i<a;i++) {
for(int j=0;j<b;j++)
{ cout<<matrix[i][j];
cout<<"\t";
}
cout<<"\n";
}
getch();
return 0;
}

m = row[0].length;
n = row.length;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(a[i][j] == 0)
fill(a,i,j)
replaceAllMinusOneWithZero(a);
return a

fill(a,i,j)
for(int x =0;x<a[0].length;x++)
if(a[x][j] == 1)
a[x][j] = -1;
for(int y =0;y<a.length;y++)
if(a[i][y] == 1)
a[i][y] = -1;

O(1) space and O(n*m) time:
1) travel normal row and column way in a matrix using two loops.. let it is i,j.. initially flag=0
2)if at any point v encounter 0 thn make flag=1 and make all elements upward of this column as 0.
3) if step 2 is not satisfied then check whether element just above it is 0 or not.. if it is thn make current element as 0 but do no change flag.. (this step is to make all elements down to original 0 element as 0)
4) now travel ahead in the same row to check for further 0s. if again zero is found then make all elements upward in the same row as 0..
5) when u reach end of row, then check whether flag is 1 or not.. if it is 1 then make complete row as 0..
6) go to next row and make flag=0 and repeat all above processes..

This way v r just making all elements above to 0 as zero and changing flag as 1 .. if current is not zero thn check upward element and if it zero thn make current element 0 but do no change flag..

Hope this HELPS...