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
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Courtesy: Vibhaj
Hints: No hint buddy :P. Hit again for solution. |
|
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:
1. Time : O(N^2)
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];
}
}
}
|
|
|
Posts
