Given a matrix of size n x m filled with 0′s and 1′s
e.g.:
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
if the matrix has 1 at (i,j), fill the column j and row i with 1′s
i.e., we get:
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
Method (Use two temporary arrays)
1) Create two temp array row[M] and col[N]. Initialize all values as 0.
2) Traverse the input matrix mat[M][N]. If you see an entry mat[i][j] as true, then mark row[i] and col[j] as true.
3) Traverse the input matrix mat[M][N] again. For each entry mat[i][j], check the values of row[i] and col[j]. If any of the two values (row[i] or col[j]) is true, then mark mat[i][j] as true.
Implementation:
void modifyMatrix(bool mat[R][C]) { bool row[R]; bool col[C]; int i, j; // Initialize all values of row[] and col[] as 0 for (i = 0; i < R; i++) { row[i] = 0; } for (i = 0; i < C; i++) { col[i] = 0; } for (i = 0; i < R; i++) { for (j = 0; j < C; j++) { if (mat[i][j] == 1) { row[i] = 1; col[j] = 1; } } } /* Modify the input matrix mat[] using the above constructed row[] and col[] arrays */ for (i = 0; i < R; i++) { for (j = 0; j < C; j++) { if ( row[i] == 1 || col[j] == 1 ) { mat[i][j] = 1; } } } }
Time Complexity: O(M*N)
Auxiliary Space: O(M + N)
Source: Boolean Matrix Question
although it has a higher time complexity, but I think this shall work too:
for (i = 0; i < R; i++)
{
for (j = 0; j < C; j++)
{
S[i][j]=0;
for (k = 0; k< R; k++)
{
if (M[k][j]==1)
{
S[i][j]=1;
break;
for(l=0; l<C; l++)
{
if (M[i][l]==1)
{
S[i][j]=1;
break;
}
}
}
}
}
}
what it does is that for each element it checks the entire corresponding column and row.
if any of the scanned positions includes a "1", the element is made "1". Else, it remains "0".
Do you think it should work?. I have, of course not included the minute details and definitions.