Zero the matrix

Given a N x N matrix with 0s and 1s. Devise an algorithm such that whenever you encounter a 0 make the corresponding row and column elements 0.

Eg.
Input  
1 0 1 1 0
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
0 0 1 1 0

Output
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0

Solution :

We keep two arrays for rows and columns with 0 indicating the corresponding row/column contains at least one 0.
Finally we use these arrays to set the required cells to 0.

Complexity :

• Time : O(N^2)
• Space : O(N)

Code :

void matrix_set_zero(int *input, int N){

int *row = new int[N];
int *col = new int[N];

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

row[i] = col[i] = 1;

}

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

for(int j=0; j<N; j++){

row[i] &= input[i][j];
col[j] &= input[i][j];

}

}

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

for(int j=0; j<N; j++){

input[i][j] = row[i] & col[j];

}

}

}