Given a Boolean Matrix, find k such that all elements in k'th row are 0 and k'th column are 1. - GeeksforGeeks
Given a square boolean matrix mat[n][n], find k such that all elements in k'th row are 0 and all elements in k'th column are 1. The value of mat[k][k] can be anything (either 0 or 1). If no such k exists, return -1.
An Efficient Solution can solve this problem in O(n) time. The solution is based on below facts.
1) There can be at most one k that can be qualified to be an answer (Why? Note that if k’th row has all 0’s probably except mat[k][k], then no column can have all 1′)s.
2) If we traverse the given matrix from a corner (preferably from top right and bottom left), we can quickly discard complete row or complete column based on below rules.
….a) If mat[i][j] is 0 and i != j, then column j cannot be the solution.
….b) If mat[i][j] is 1 and i != j, then row i cannot be the solution.
A Simple Solution is check all rows one by one. If we find a row ‘i’ such that all elements of this row are 0 except mat[i][i] which may be either 0 or 1, then we check all values in column ‘i’. If all values are 1 in the column, then we return i. Time complexity of this solution is O(n2).
http://www.zrzahid.com/find-k-such-that-kth-row-is-all-zero-and-kth-col-is-all-one-in-a-matrix/
http://blueocean-penn.blogspot.com/2015/09/find-values-at-kth-row-are-0-and-kth.html
Another way to travel from top-left corner, we start with 0th row:
go right if the element is 0, if we reach the end of row, then that means: 1) this rth row is potential candidate; 2) the columns/rows from r+1 to n-1 are not candidate; And we check kth row/col values.
go down if the element is 1, for the current row is no longer qualifies.
Since we either go right or go down, then time complexity is O(n)
public static int findKthRow(int[][] mat){
int n = mat.length;
int row = 0;
while(row<n-1){
int col = row + 1;
//move from left to right at current row
while(col<n && mat[row][col] == 0){
col++;
}
/*
* if we reach the last column of current row, then
* this row is candidate and
* rest of rows are not candidates
* otherwise
* we go down one row below
*/
if(col == n){
//check if this row is qualified
return checkKthRowCol(mat, row)?row:-1;
}else{
row++;
}
}
return checkKthRowCol(mat, row)?row:-1;
}
private static boolean checkKthRowCol(int[][] mat, int k){
int n = mat.length;
for(int i = 0; i<n; i++){
if(i==k)
continue;
else{
if(mat[k][i]==1 || mat[i][k]==0)
return false;
}
}
return true;
}
Read full article from Given a Boolean Matrix, find k such that all elements in k'th row are 0 and k'th column are 1. - GeeksforGeeks
Given a square boolean matrix mat[n][n], find k such that all elements in k'th row are 0 and all elements in k'th column are 1. The value of mat[k][k] can be anything (either 0 or 1). If no such k exists, return -1.
An Efficient Solution can solve this problem in O(n) time. The solution is based on below facts.
1) There can be at most one k that can be qualified to be an answer (Why? Note that if k’th row has all 0’s probably except mat[k][k], then no column can have all 1′)s.
2) If we traverse the given matrix from a corner (preferably from top right and bottom left), we can quickly discard complete row or complete column based on below rules.
….a) If mat[i][j] is 0 and i != j, then column j cannot be the solution.
….b) If mat[i][j] is 1 and i != j, then row i cannot be the solution.
1) Start from top right corner, i.e., i = 0, j = n-1.
Initialize result as -1.
2) Do following until we find the result or reach outside the matrix.
......a) If mat[i][j] is 0, then check all elements on left of j in current row.
.........If all elements on left of j are also 0, then set result as i. Note
.........that i may not be result, but if there is a result, then it must be i
.........(Why? we reach mat[i][j] after discarding all rows above it and all
.........columns on right of it)
.........If all left side elements of i'th row are not 0, them this row cannot
.........be a solution, increment i.
......b) If mat[i][j] is 1, then check all elements below i in current column.
.........If all elements below i are 1, then set result as j. Note that j may
......... not be result, but if there is a result, then it must be j
.........If all elements of j'th column are not 1, them this column cannot be a
.........solution decrement j.
3) If result is -1, return it.
4) Else check validity of result by checking all row and column
elements of result
Time complexity of this solution is O(n). Note that we traverse at most 2n elements in the main while loop.
int find(bool arr[n][n]){ // Start from top-most rightmost corner // (We could start from other corners also) int i=0, j=n-1; // Initialize result int res = -1; // Find the index (This loop runs at most 2n times, we either // increment row number or decrement column number) while (i<n && j>=0) { // If current element is 0, then this row may be a solution if (arr[i][j] == 0) { // Check for all elements in this row while (j >= 0 && (arr[i][j] == 0 || i == j)) j--; // If all values are 0, then store this row as result if (j == -1) { res = i; break; } // We reach here if we found a 1 in current row, so this // row cannot be a solution, increment row number else i++; } else // If current element is 1 { // Check for all elements in this column while (i<n && (arr[i][j] == 1 || i == j)) i++; // If all elements are 1 if (i == n) { res = j; break; } // We reach here if we found a 0 in current column, so this // column cannot be a solution, increment column number else j--; } } // If we could not find result in above loop, then result doesn't exist if (res == -1) return res; // Check if above computed res is valid for (int i=0; i<n; i++) if (res != i && arr[i][res] != 1) return -1; for (int j=0; j<n; j++) if (res != j && arr[res][j] != 0) return -1; return res;}A Simple Solution is check all rows one by one. If we find a row ‘i’ such that all elements of this row are 0 except mat[i][i] which may be either 0 or 1, then we check all values in column ‘i’. If all values are 1 in the column, then we return i. Time complexity of this solution is O(n2).
http://www.zrzahid.com/find-k-such-that-kth-row-is-all-zero-and-kth-col-is-all-one-in-a-matrix/
there can be at most one solution of this problem because if we have more than one solution then we have more than one row that satisfies the constraint which automatically tells us that more than one columns in the row has 1, which in turn contradicts the row condition. So, we there is at most one such k.
We can actually start from a corner, let’s say the top-left. If this corner contains a 0 then we try to validate if this row can be a candidate. If all other values int the row are zero then it is a candidate row and we need to check for column condition. Otherwise, if there is a one value in the row then this row can’t be the solution and we go to next row.
On the other hand if the corner was a 1 then we have to check the validity of the column. If all other column values are 1 then this is a candidate column and we need to validate the row constraint. Otherwise, if there was a zero in the column then this column can’t be the candidate and we go to next column.
Each time, we are either incrementing a row or a column. So, will visit at most visit 2n numbers of element in this way and hence the time complexity is O(n).
public static int findKthRowCol(int mat[][]){ int n = mat.length; int m = mat[0].length; int i = 0; int j = 0; int candidate = -1; while(i < n && j < m){ //check the row for all zero if(mat[i][j] == 0){ int k = j+1; while(k < m && mat[i][k] == 0){ k++; } if(k == m){ candidate = i; break; } //if not all zero in this row, then this row can't be the candidate else{ i++; } } //check the column for all ones else{ int k = i+1; while(k < n && mat[k][j] == 0){ k++; } if(k == n){ candidate = i; break; } //if not all are 1 then this col can't be the candidate else{ j++; } } } //we found a row/cold candidate, validate the rowand columnd if(candidate != -1){ for(j = 0; j<n; j++){ if(j != candidate && mat[candidate][j] != 0){ return -1; } } for(i = 0; i<n; i++){ if(i != candidate && mat[i][candidate] != 1){ return -1; } } return candidate; } return candidate; }
Another way to travel from top-left corner, we start with 0th row:
go right if the element is 0, if we reach the end of row, then that means: 1) this rth row is potential candidate; 2) the columns/rows from r+1 to n-1 are not candidate; And we check kth row/col values.
go down if the element is 1, for the current row is no longer qualifies.
Since we either go right or go down, then time complexity is O(n)
public static int findKthRow(int[][] mat){
int n = mat.length;
int row = 0;
while(row<n-1){
int col = row + 1;
//move from left to right at current row
while(col<n && mat[row][col] == 0){
col++;
}
/*
* if we reach the last column of current row, then
* this row is candidate and
* rest of rows are not candidates
* otherwise
* we go down one row below
*/
if(col == n){
//check if this row is qualified
return checkKthRowCol(mat, row)?row:-1;
}else{
row++;
}
}
return checkKthRowCol(mat, row)?row:-1;
}
private static boolean checkKthRowCol(int[][] mat, int k){
int n = mat.length;
for(int i = 0; i<n; i++){
if(i==k)
continue;
else{
if(mat[k][i]==1 || mat[i][k]==0)
return false;
}
}
return true;
}
Read full article from Given a Boolean Matrix, find k such that all elements in k'th row are 0 and k'th column are 1. - GeeksforGeeks
