# Boolean Matrix Question

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

### One Thought on “Boolean Matrix Question”

1. 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.