**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 -

- 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.
- 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.
- Now set all the cells in first row and column as false.
- Traverse the input matrix and see if mat[i][j] is true, then set mat[0][j] and mat[i][0] as true.
- 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.
- 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)

## No comments:

## Post a Comment