Given a Boolean Matrix, find k such that all elements in k’th row are 0 and k’th column are 1.
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.
Examples:
Input: bool mat[n][n] = { {1, 0, 0, 0}, {1, 1, 1, 0}, {1, 1, 0, 0}, {1, 1, 1, 0}, }; Output: 0 All elements in 0'th row are 0 and all elements in 0'th column are 1. mat[0][0] is 1 (can be any value) Input: bool mat[n][n] = {{0, 1, 1, 0, 1}, {0, 0, 0, 0, 0}, {1, 1, 1, 0, 0}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}}; Output: 1 All elements in 1'st row are 0 and all elements in 1'st column are 1. mat[1][1] is 0 (can be any value) Input: bool mat[n][n] = {{0, 1, 1, 0, 1}, {0, 0, 0, 0, 0}, {1, 1, 1, 0, 0}, {1, 0, 1, 1, 0}, {1, 1, 1, 1, 1}}; Output: -1 There is no k such that k'th row elements are 0 and k'th column elements are 1.
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).
An Efficient Solution can solve this problem in O(n) time. The solution is based on below facts.
- 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.
- 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.
- If mat[i][j] is 0 and i != j, then column j cannot be the solution.
- If mat[i][j] is 1 and i != j, then row i cannot be the solution.
Below is the complete algorithm based on above observations.
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
Below is the implementation based on the above idea.
C++
// C++ program to find i such that all entries in i'th row are 0 // and all entries in i't column are 1 #include <iostream> using namespace std; #define n 5 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; } /* Driver program to test above functions */ int main() { bool mat[n][n] = {{0, 0, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 0}, {0, 0, 0, 0, 0}, {1, 1, 1, 1, 1}}; cout << find(mat); return 0; } |
Java
// Java program to find i such that all entries in i'th row are 0 // and all entries in i't column are 1 import java.io.*; public class GFG { static int n = 5 ; static int find( boolean arr[][]) { // 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 false, then this row may be a solution if (arr[i][j] == false ) { // Check for all elements in this row while (j >= 0 && (arr[i][j] == false || i == j)) { j--; } // If all values are false, 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] == true || 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 k = 0 ; k < n; k++) { if (res != k && arr[k][res] != true ) { return - 1 ; } } for ( int l = 0 ; l < n; l++) { if (res != l && arr[res][l] != false ) { return - 1 ; } } return res; } /* Driver program to test above functions */ public static void main(String[] args) { boolean mat[][] = {{ false , false , true , true , false }, { false , false , false , true , false }, { true , true , true , true , false }, { false , false , false , false , false }, { true , true , true , true , true }}; System.out.println(find(mat)); } } /* This Java code is contributed by PrinciRaj1992*/ |
Python3
''' Python program to find k such that all elements in k'th row are 0 and k'th column are 1''' def find(arr): # store length of the array n = len (arr) # start from top right-most corner i = 0 j = n - 1 # initialise result res = - 1 # find the index (This loop runs at most 2n times, we # either increment row number or decrement column number) while i < n and j > = 0 : # if the current element is 0, then this row may be a solution if arr[i][j] = = 0 : # check for all the elements in this row while j > = 0 and (arr[i][j] = = 0 or i = = j): j - = 1 # if all values are 0, update result as row number if j = = - 1 : res = i break # if found a 1 in current row, the row can't be a # solution, increment row number else : i + = 1 # if the current element is 1 else : #check for all the elements in this column while i < n and (arr[i][j] = = 1 or i = = j): i + = 1 # if all elements are 1, update result as col number if i = = n: res = j break # if found a 0 in current column, the column can't be a # solution, decrement column number else : j - = 1 # if we couldn't find result in above loop, result doesn't exist if res = = - 1 : return res # check if the above computed res value is valid for i in range ( 0 , n): if res ! = i and arr[i][res] ! = 1 : return - 1 for j in range ( 0 , j): if res ! = j and arr[res][j] ! = 0 : return - 1 ; return res; # test find(arr) function arr = [ [ 0 , 0 , 1 , 1 , 0 ], [ 0 , 0 , 0 , 1 , 0 ], [ 1 , 1 , 1 , 1 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 1 , 1 , 1 , 1 , 1 ] ] print (find(arr)) |
C#
// C# program to find i such that all entries in i'th row are 0 // and all entries in i't column are 1 using System; public class GFG{ static int n = 5; static int find( bool [,]arr) { // 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 false, then this row may be a solution if (arr[i,j] == false ) { // Check for all elements in this row while (j >= 0 && (arr[i,j] == false || i == j)) { j--; } // If all values are false, 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] == true || 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 k = 0; k < n; k++) { if (res != k && arr[k,res] != true ) { return -1; } } for ( int l = 0; l < n; l++) { if (res != l && arr[res,l] != false ) { return -1; } } return res; } /* Driver program to test above functions */ public static void Main() { bool [,]mat = {{ false , false , true , true , false }, { false , false , false , true , false }, { true , true , true , true , false }, { false , false , false , false , false }, { true , true , true , true , true }}; Console.WriteLine(find(mat)); } } // This code is contributed by PrinciRaj1992 |
PHP
<?php // PHP program to find i such that all // entries in i'th row are 0 and all // entries in i'th column are 1 function find(& $arr ) { $n = 5; // Start from top-most rightmost corner // (We could start from other corners also) $i = 0; $j = $n - 1; // Initialize result $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 ( $i = 0; $i < $n ; $i ++) if ( $res != $i && $arr [ $i ][ $res ] != 1) return -1; for ( $j = 0; $j < $n ; $j ++) if ( $res != $j && $arr [ $res ][ $j ] != 0) return -1; return $res ; } // Driver Code $mat = array ( array (0, 0, 1, 1, 0), array (0, 0, 0, 1, 0), array (1, 1, 1, 1, 0), array (0, 0, 0, 0, 0), array (1, 1, 1, 1, 1)); echo (find( $mat )); // This code is contributed by Shivi_Aggarwal ?> |
Javascript
<script> // JavaScript program to find i such that // all entries in i'th row are 0 // and all entries in i't column are 1 var n = 5; function find(arr) { // Start from top-most rightmost corner // (We could start from other corners also) var i = 0, j = n - 1; // Initialize result var 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 false, // then this row may be a solution if (arr[i][j] == false ) { // Check for all elements in this row while (j >= 0 && (arr[i][j] == false || i == j)) { j--; } // If all values are false, // 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] == true || 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 ( var k = 0; k < n; k++) { if (res != k && arr[k][res] != true ) { return -1; } } for ( var l = 0; l < n; l++) { if (res != l && arr[res][l] != false ) { return -1; } } return res; } /* Driver program to test above functions */ var mat = [[ false , false , true , true , false ], [ false , false , false , true , false ], [ true , true , true , true , false ], [ false , false , false , false , false ], [ true , true , true , true , true ]]; document.write(find(mat)); </script> |
3
Time complexity of this solution is O(n). Note that we traverse at most 2n elements in the main while loop.
Auxiliary Space: O(1)