A NxN binary matrix is given. If a row contains a 0 all element in the row will be set to 0 and if a column contains a 0 all element of the colum set 0

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


Data Structure Used: 2D Array

Algorithm(Requires Two Passes Over Matrix)
1.Use two Integer or Boolean array in 1st pass over Matrix set row & col set 1 according to
content of a[i][j]
2. in second pass over matrix for all i,j check row & col array is its 1 then set a[i]j]=0 in
matrix else continue

1st Solution (Using Two Linear Boolean array of row & column)

class matrix_zero
{


public static void setZeros(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = 1;
column[j] = 1;
}
}
}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
}

public static void main(String a[])
{
int ar[][]=new int[][]{{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}
};


setZeros(ar);

for (int i = 0; i <5 data-blogger-escaped-br="" data-blogger-escaped-i=""> {
for (int j = 0; j < 5;j++)
{
System.out.println(ar[i][j]);

}
System.out.println();

}

}


}

Time Complexity O(N^2) //two Passes over Matrix
Space Complexity O(2*N)
Run Here http://ideone.com/ntrdr


2nd Solution Optimize


Algorithm: (Updated)

This method is a space optimized version of above method 1. This method uses the first row and first column of the input matrix in place of the auxiliary arrays row[] and col[] of method 1. So what we do is: first take care of first row and column and store the info about these two in two flag variables rowFlag and colFlag. Once we have this info, we can use first row and first column as auxiliary arrays and apply method 1 for submatrix (matrix excluding first row and first column) of size (M-1)*(N-1).

1) Scan the first row and set a variable rowFlag to indicate whether we need to set all 1s in first row or not.
2) Scan the first column and set a variable colFlag to indicate whether we need to set all 1s in first column or not.
3) Use first row and first column as the auxiliary arrays row[] and col[] respectively, consider the matrix as submatrix starting from second row and second column and apply method 1.
4) Finally, using rowFlag and colFlag, update first row and first column if needed.

Time Complexity: O(M*N)
Auxiliary Space: O(1)

Time Complexity O(N^2)
Space Complexity O(1)