WAP to

Binary Matrix Problem

Problem: An NxN binary Matrix is given. If a row contains a 0 all element in the row will be sent to 0 and if a column contains a 0 all element of the column will be set to 0. You have to do it in O(1) space.

Example:
Input array:
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
Result array:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0


Solution:
Step 1: Store matrix [0][0] value in a temporary variable (Space Complicity: O(1) ).


Step 2: Apply & operation on first column and save it into Temp.


Step 3: Apply & operation on first row and save it into matrix [0][0].



Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
And value in Temp = 0

Step 4: Apply & operation on each row and save the result in the first cell of each row. Here i starts from 1 to n-1.





Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
And value in Temp = 0

Step 5: Apply & operation on each column and save the result in the first cell of each column. Here j starts from 1 to n-1.





Now 2D Matrix Array becomes:
0 0 1 1 0
0 1 1 1 0
1 1 1 1 1
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0
Step 6: Now to find the value at matrix[i][j], you have to do a[i][0] & a[0][j]. Here I and j start from 1 to n-1




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 1 1 1 1
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0





Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 1 1 1
1 1 1 1 1
And value in Temp = 0




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 0 0
1 1 1 1 1
And value in Temp = 0




Now 2D Matrix Array becomes:
0 0 1 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 0 0
1 0 1 1 0
And value in Temp = 0
Step 7: Now to find the value at matrix [0][i] and matrix[j][0]. If matrix [0][0] is equal to 0 then make value 0 all the matrix[0][i] else remain unchanged. If Temp is equal to 0 the make value 0 all the matrix [j][0] else remain unchanged.
If (matrix [0][0] == 0)
Then



If (Temp == 0)
Then




Now 2D Matrix Array becomes:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
And value in Temp = 0

Step 8: Now to find the value at matrix [0][0], you need to do matrix [0][0] & Temp and save it into matrix [0][0].

Now 2D Matrix Array becomes:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
And value in Temp = 0
Step 9: Print your matrix and exit.
Result 2D Matrix array:
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0


Working Code