OLA Question: Modify Boolean matrix

Problem: Given a Boolean matrix , modify it such that if a matrix cell mat[i][j] is true then make all the cells of i^th row and j^th column as true.

Solution: Following are the steps -

1. Traverse the first row and set a variable firstRowFlag to indicate whether all the cells in first row should be set to true or not.
2. Similarly traverse the first column and set a variable firstColFlag to indicate whether all the cells in first column should be set to true or not.
3. Now set all the cells in first row and column as false.
4. Traverse the input matrix and see if mat[i][j] is true, then set mat[0][j] and mat[i][0] as true.
5. Traverse the input matrix and for each entry mat[i][j], check if either mat[0][j] or mat[i][0] is true, then set mat[i][j] to true.
6. Now, using firstRowFlag and firstColFlag, update first row and first column if needed.

Implementation:

void modifyBoolMatrix(bool **mat, int M, int N)

{

bool firstRowFlag = false, firstColFlag = false;

for(int i = 0; i < N; ++i)

{

if(mat[0][i])

{

mat[0][i] = false;

firstRowFlag = true;

}

}

for(int i = 0; i < M; ++i)

{

if(mat[i][0])

{

mat[i][0] = false;

firstColFlag = true;

}

}

for(int i = 1; i < M; ++i)

{

for(int j = 1; j < N; ++j)

{

if(mat[i][j])

{

mat[0][j] = true;

mat[i][0] = true;

}

}

}

for(int i = 1; i < M; ++i)

{

for(int j = 1; j < N; ++j)

{

if(mat[0][j] || mat[i][0])

mat[i][j] = true;

}

}

if(firstRowFlag)

{

for(int i = 0; i < N; ++i)

mat[0][i] = true;

}

if(firstColFlag)

{

for(int i = 0; i < M; ++i)

mat[i][0] = true;

}

}

Complexity: O(M * N)