Find if there is a rectangle in binary matrix with corners as 1
There is a given binary matrix, we need to find if there exists any rectangle or square in the given matrix whose all four corners are equal to
Examples:
Input : mat[][] = { 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1} Output : Yes as there exists- 1 0 1 0 1 0 1 0 1
Brute Force Approach:
We start scanning the matrix whenever we find a 1 at any index then we try for all the combinations for index with which we can form the rectangle.
Algorithm:
for i = 1 to rows for j = 1 to columns if matrix[i][j] == 1 for k=i+1 to rows for l=j+1 to columns if (matrix[i][l]==1 && matrix[k][j]==1 && m[k][l]==1) return true return false
Implementation:
C++
// A brute force approach based CPP program to // find if there is a rectangle with 1 as corners. #include <bits/stdc++.h> using namespace std; // Returns true if there is a rectangle with // 1 as corners. bool isRectangle( const vector<vector< int > >& m) { // finding row and column size int rows = m.size(); if (rows == 0) return false ; int columns = m[0].size(); // scanning the matrix for ( int y1 = 0; y1 < rows; y1++) for ( int x1 = 0; x1 < columns; x1++) // if any index found 1 then try // for all rectangles if (m[y1][x1] == 1) for ( int y2 = y1 + 1; y2 < rows; y2++) for ( int x2 = x1 + 1; x2 < columns; x2++) if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1) return true ; return false ; } // Driver code int main() { vector<vector< int > > mat = { { 1, 0, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 } }; if (isRectangle(mat)) cout << "Yes" ; else cout << "No" ; } |
Java
// A brute force approach based CPP program to // find if there is a rectangle with 1 as corners. public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static boolean isRectangle( int m[][]) { // finding row and column size int rows = m.length; if (rows == 0 ) return false ; int columns = m[ 0 ].length; // scanning the matrix for ( int y1 = 0 ; y1 < rows; y1++) for ( int x1 = 0 ; x1 < columns; x1++) // if any index found 1 then try // for all rectangles if (m[y1][x1] == 1 ) for ( int y2 = y1 + 1 ; y2 < rows; y2++) for ( int x2 = x1 + 1 ; x2 < columns; x2++) if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1 ) return true ; return false ; } public static void main(String args[]) { int mat[][] = { { 1 , 0 , 0 , 1 , 0 }, { 0 , 0 , 1 , 0 , 1 }, { 0 , 0 , 0 , 1 , 0 }, { 1 , 0 , 1 , 0 , 1 } }; if (isRectangle(mat)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Gaurav Tiwari |
Python3
# A brute force approach based Python3 program to # find if there is a rectangle with 1 as corners. # Returns true if there is a rectangle # with 1 as corners. def isRectangle(m): # finding row and column size rows = len (m) if (rows = = 0 ): return False columns = len (m[ 0 ]) # scanning the matrix for y1 in range (rows): for x1 in range (columns): # if any index found 1 then # try for all rectangles if (m[y1][x1] = = 1 ): for y2 in range (y1 + 1 , rows): for x2 in range (x1 + 1 , columns): if (m[y1][x2] = = 1 and m[y2][x1] = = 1 and m[y2][x2] = = 1 ): return True return False # Driver code mat = [[ 1 , 0 , 0 , 1 , 0 ], [ 0 , 0 , 1 , 0 , 1 ], [ 0 , 0 , 0 , 1 , 0 ], [ 1 , 0 , 1 , 0 , 1 ]] if (isRectangle(mat)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by mohit kumar 29 |
C#
// A brute force approach based C# program to // find if there is a rectangle with 1 as corners. using System; public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static Boolean isRectangle( int [, ] m) { // finding row and column size int rows = m.GetLength(0); if (rows == 0) return false ; int columns = m.GetLength(1); // scanning the matrix for ( int y1 = 0; y1 < rows; y1++) for ( int x1 = 0; x1 < columns; x1++) // if any index found 1 then try // for all rectangles if (m[y1, x1] == 1) for ( int y2 = y1 + 1; y2 < rows; y2++) for ( int x2 = x1 + 1; x2 < columns; x2++) if (m[y1, x2] == 1 && m[y2, x1] == 1 && m[y2, x2] == 1) return true ; return false ; } // Driver code public static void Main(String[] args) { int [, ] mat = { { 1, 0, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 } }; if (isRectangle(mat)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code contributed by Rajput-Ji |
Javascript
<script> // A brute force approach based Javascript program to // find if there is a rectangle with 1 as corners. // Returns true if there is a rectangle with // 1 as corners. function isRectangle(m) { // finding row and column size let rows = m.length; if (rows == 0) return false ; let columns = m[0].length; // scanning the matrix for (let y1 = 0; y1 < rows; y1++) for (let x1 = 0; x1 < columns; x1++) // if any index found 1 then try // for all rectangles if (m[y1][x1] == 1) for (let y2 = y1 + 1; y2 < rows; y2++) for (let x2 = x1 + 1; x2 < columns; x2++) if (m[y1][x2] == 1 && m[y2][x1] == 1 && m[y2][x2] == 1) return true ; return false ; } let mat = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]]; if (isRectangle(mat)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by patel2127 </script> |
Yes
Time Complexity: O(m2 * n2)
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach:
- Scan from top to down, line by line
- For each line, remember each combination of 2 1’s and push that into a hash-set
- If we ever find that combination again in a later line, we get our rectangle
Below is the implementation of the above approach:
C++
// An efficient approach based CPP program to // find if there is a rectangle with 1 as // corners. #include <bits/stdc++.h> using namespace std; // Returns true if there is a rectangle with // 1 as corners. bool isRectangle( const vector<vector< int > >& matrix) { // finding row and column size int rows = matrix.size(); if (rows == 0) return false ; int columns = matrix[0].size(); // map for storing the index of combination of 2 1's unordered_map< int , unordered_set< int > > table; // scanning from top to bottom line by line for ( int i = 0; i < rows; ++i) { for ( int j = 0; j < columns - 1; ++j) { for ( int k = j + 1; k < columns; ++k) { // if found two 1's in a column if (matrix[i][j] == 1 && matrix[i][k] == 1) { // check if there exists 1's in same // row previously then return true // we don't need to check (j, k) pair // and again (k, j) pair because we always // store pair in ascending order and similarly // check in ascending order, i.e. j always less // than k. if (table.find(j) != table.end() && table[j].find(k) != table[j].end()) return true ; // store the indexes in hashset table[j].insert(k); } } } } return false ; } // Driver code int main() { vector<vector< int > > mat = { { 1, 0, 0, 1, 0 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 0 }, { 1, 1, 1, 1, 0 } }; if (isRectangle(mat)) cout << "Yes" ; else cout << "No" ; } // This code is improved by Gautam Agrawal |
Java
// An efficient approach based Java program to // find if there is a rectangle with 1 as // corners. import java.util.HashMap; import java.util.HashSet; public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static boolean isRectangle( int matrix[][]) { // finding row and column size int rows = matrix.length; if (rows == 0 ) return false ; int columns = matrix[ 0 ].length; // map for storing the index of combination of 2 1's HashMap<Integer, HashSet<Integer> > table = new HashMap<>(); // scanning from top to bottom line by line for ( int i = 0 ; i < rows; i++) { for ( int j = 0 ; j < columns - 1 ; j++) { for ( int k = j + 1 ; k < columns; k++) { // if found two 1's in a column if (matrix[i][j] == 1 && matrix[i][k] == 1 ) { // check if there exists 1's in same // row previously then return true if (table.containsKey(j) && table.get(j).contains(k)) { return true ; } if (table.containsKey(k) && table.get(k).contains(j)) { return true ; } // store the indexes in hashset if (!table.containsKey(j)) { HashSet<Integer> x = new HashSet<>(); x.add(k); table.put(j, x); } else { table.get(j).add(k); } if (!table.containsKey(k)) { HashSet<Integer> x = new HashSet<>(); x.add(j); table.put(k, x); } else { table.get(k).add(j); } } } } } return false ; } public static void main(String args[]) { int mat[][] = { { 1 , 0 , 0 , 1 , 0 }, { 0 , 0 , 1 , 0 , 1 }, { 0 , 0 , 0 , 1 , 0 }, { 1 , 0 , 1 , 0 , 1 } }; if (isRectangle(mat)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Gaurav Tiwari |
Python3
# An efficient approach based Python program # to find if there is a rectangle with 1 as # corners. # Returns true if there is a rectangle # with 1 as corners. def isRectangle(matrix): # finding row and column size rows = len (matrix) if (rows = = 0 ): return False columns = len (matrix[ 0 ]) # map for storing the index of # combination of 2 1's table = {} # scanning from top to bottom # line by line for i in range (rows): for j in range (columns - 1 ): for k in range (j + 1 , columns): # if found two 1's in a column if (matrix[i][j] = = 1 and matrix[i][k] = = 1 ): # check if there exists 1's in same # row previously then return true if (j in table and k in table[j]): return True if (k in table and j in table[k]): return True # store the indexes in hashset if j not in table: table[j] = set () if k not in table: table[k] = set () table[j].add(k) table[k].add(j) return False # Driver Code if __name__ = = '__main__' : mat = [[ 1 , 0 , 0 , 1 , 0 ], [ 0 , 0 , 1 , 0 , 1 ], [ 0 , 0 , 0 , 1 , 0 ], [ 1 , 0 , 1 , 0 , 1 ]] if (isRectangle(mat)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by SHUBHAMSINGH10 |
C#
// An efficient approach based C# program to // find if there is a rectangle with 1 as // corners. using System; using System.Collections.Generic; public class FindRectangle { // Returns true if there is a rectangle with // 1 as corners. static bool isRectangle( int [, ] matrix) { // finding row and column size int rows = matrix.GetLength(0); if (rows == 0) return false ; int columns = matrix.GetLength(1); // map for storing the index of combination of 2 1's Dictionary< int , HashSet< int > > table = new Dictionary< int , HashSet< int > >(); // scanning from top to bottom line by line for ( int i = 0; i < rows; i++) { for ( int j = 0; j < columns - 1; j++) { for ( int k = j + 1; k < columns; k++) { // if found two 1's in a column if (matrix[i, j] == 1 && matrix[i, k] == 1) { // check if there exists 1's in same // row previously then return true if (table.ContainsKey(j) && table[j].Contains(k)) { return true ; } if (table.ContainsKey(k) && table[k].Contains(j)) { return true ; } // store the indexes in hashset if (!table.ContainsKey(j)) { HashSet< int > x = new HashSet< int >(); x.Add(k); table.Add(j, x); } else { table[j].Add(k); } if (!table.ContainsKey(k)) { HashSet< int > x = new HashSet< int >(); x.Add(j); table.Add(k, x); } else { table[k].Add(j); } } } } } return false ; } public static void Main(String[] args) { int [, ] mat = { { 1, 0, 0, 1, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 0, 1, 0 }, { 1, 0, 1, 0, 1 } }; if (isRectangle(mat)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // An efficient approach based Javascript program to // find if there is a rectangle with 1 as // corners. // Returns true if there is a rectangle with // 1 as corners. function isRectangle(matrix) { // finding row and column size let rows = matrix.length; if (rows == 0) return false ; let columns = matrix[0].length; // map for storing the index of // combination of 2 1's let table = new Map(); // scanning from top to bottom line by line for (let i = 0; i < rows; i++) { for (let j = 0; j < columns - 1; j++) { for (let k = j + 1; k < columns; k++) { // if found two 1's in a column if (matrix[i][j] == 1 && matrix[i][k] == 1) { // check if there // exists 1's in same // row previously then // return true if (table.has(j) && table.get(j).has(k)) { return true ; } if (table.has(k) && table.get(k).has(j)) { return true ; } // store the indexes in hashset if (!table.has(j)) { let x = new Set(); x.add(k); table.set(j, x); } else { table.get(j).add(k); } if (!table.has(k)) { let x = new Set(); x.add(j); table.set(k, x); } else { table.get(k).add(j); } } } } } return false ; } let mat = [[ 1, 0, 0, 1, 0 ], [ 0, 0, 1, 0, 1 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 1, 0, 1 ]]; if (isRectangle(mat)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by unknown2108 </script> |
Yes
Time Complexity: O(n*m2)
Auxiliary Space: O(n*m)
More Efficient Approach
The previous approach scans through every pair of column indexes to find each combination of 2 1’s.
- To more efficiently find each combination of 2 1’s, convert each row into a set of column indexes.
- Then, select pairs of column indexes from the row set to quickly get each combination of 2 1’s.
- If a pair of column indexes appears more than once, then there is a rectangle whose corners are 1’s.
- The runtime becomes O(m*n+n*n*log(n*n)). This is because there are m*n cells in the matrix and there are at most O(n^2) combinations of column indexes and we are using a map which will store every entry in log(n) time.
- Also, if n > m, then by first transposing the matrix, the runtime becomes O(m*n+m*m*log(m*m)).
Notice that min{m*n+n*n*log(n*n), m*n+m*m*log(m*m)} is O(m*n + p*p*log(p*p)), p=max(n,m).
Below is the implementation of the above approach:
C++
// C++ implementation comes from: // https://github.com/MichaelWehar/FourCornersProblem // Written by Niteesh Kumar and Michael Wehar // References: // [1] F. Mráz, D. Prusa, and M. Wehar. // Two-dimensional Pattern Matching against // Basic Picture Languages. CIAA 2019. // [2] D. Prusa and M. Wehar. Complexity of // Searching for 2 by 2 Submatrices in Boolean // Matrices. DLT 2020. #include <bits/stdc++.h> using namespace std; bool searchForRectangle( int rows, int cols, vector<vector< int >> mat) { // Make sure that matrix is non-trivial if (rows < 2 || cols < 2) { return false ; } // Create map int num_of_keys; map< int , vector< int >> adjsList; if (rows >= cols) { // Row-wise num_of_keys = rows; // Convert each row into vector of col indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i][j]) { adjsList[i].push_back(j); } } } } else { // Col-wise num_of_keys = cols; // Convert each col into vector of row indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i][j]) { adjsList[j].push_back(i); } } } } // Search for a rectangle whose four corners are 1's map<pair< int , int >, int > pairs; for ( int i = 0; i < num_of_keys; i++) { vector< int > values = adjsList[i]; int size = values.size(); for ( int j = 0; j < size - 1; j++) { for ( int k = j + 1; k < size; k++) { pair< int , int > temp = make_pair(values[j], values[k]); if (pairs.find(temp) != pairs.end()) { return true ; } else { pairs[temp] = i; } } } } return false ; } // Driver code int main() { vector<vector< int > > mat = { { 1, 0, 0, 1, 0 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 0 }, { 1, 1, 1, 1, 0 } }; if (searchForRectangle(4, 5, mat)) cout << "Yes" ; else cout << "No" ; } |
Java
// Java implementation comes from: // https://github.com/MichaelWehar/FourCornersProblem // Written by Niteesh Kumar and Michael Wehar // References: // [1] F. Mráz, D. Prusa, and M. Wehar. // Two-dimensional Pattern Matching against // Basic Picture Languages. CIAA 2019. // [2] D. Prusa and M. Wehar. Complexity of // Searching for 2 by 2 Submatrices in Boolean // Matrices. DLT 2020. import java.util.*; class GFG { // Function to search for a rectangle static boolean searchForRectangle( int rows, int cols, int [][] mat) { // Make sure that matrix is non-trivial if (rows < 2 || cols < 2 ) return false ; // Create map int num_of_keys; Map<Integer, List<Integer>> adjsList = new HashMap<>(); if (rows >= cols) { // Row-wise num_of_keys = rows; // Convert each row into vector of col indexes for ( int i = 0 ; i < rows; i++) { for ( int j = 0 ; j < cols; j++) { if (mat[i][j] == 1 ) { if (!adjsList.containsKey(i)) { List<Integer> temp = new ArrayList<>(); temp.add(j); adjsList.put(i, temp); } else { adjsList.get(i).add(j); } } } } } else { // Col-wise num_of_keys = cols; // Convert each col into vector of row indexes for ( int i = 0 ; i < rows; i++) { for ( int j = 0 ; j < cols; j++) { if (mat[i][j] == 1 ) { if (!adjsList.containsKey(j)) { List<Integer> temp = new ArrayList<>(); temp.add(i); adjsList.put(j, temp); } else { adjsList.get(j).add(i); } } } } } // Search for a rectangle // whose four corners are 1's Map<String, Integer> pairs = new HashMap<>(); for ( int i = 0 ; i < num_of_keys; i++) { List<Integer> values = adjsList.get(i); int size = values.size(); for ( int j = 0 ; j < size - 1 ; j++) { for ( int k = j + 1 ; k < size; k++) { String temp = values.get(j) + " " + values.get(k); if (pairs.containsKey(temp)) { return true ; } else { pairs.put(temp, i); } } } } return false ; } // Driver code public static void main(String[] args) { int [][] mat = { { 1 , 0 , 0 , 1 , 0 }, { 0 , 1 , 1 , 1 , 1 }, { 0 , 0 , 0 , 1 , 0 }, { 1 , 1 , 1 , 1 , 0 } }; if (searchForRectangle( 4 , 5 , mat)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Srj_27 |
Python3
# Python3 implementation comes from: # https:#github.com/MichaelWehar/FourCornersProblem # Written by Niteesh Kumar and Michael Wehar # References: # [1] F. Mráz, D. Prusa, and M. Wehar. # Two-dimensional Pattern Matching against # Basic Picture Languages. CIAA 2019. # [2] D. Prusa and M. Wehar. Complexity of # Searching for 2 by 2 Submatrices in Boolean # Matrices. DLT 2020. def searchForRectangle( rows, cols, mat) : # Make sure that matrix is non-trivial if (rows < 2 or cols < 2 ) : return False ; # Create map adjsList = dict (); if (rows > = cols): # Row-wise num_of_keys = rows; # Convert each row into vector of col indexes for i in range (rows): for j in range (cols): if (mat[i][j]): if i not in adjsList: adjsList[i] = [] adjsList[i].append(j); else : # Col-wise num_of_keys = cols; # Convert each col into vector of row indexes for i in range (rows): for j in range (cols): if (mat[i][j] = = 1 ) : if j not in adjsList: adjsList[j] = [] adjsList[j].append(i); # Search for a rectangle whose four corners are 1's pairs = dict (); for i in range (num_of_keys): values = adjsList[i]; size = len (values) for j in range (size - 1 ): for k in range (j + 1 , size): temp = (values[j], values[k]); if temp in pairs: return True ; else : pairs[temp] = i; return False ; # Driver code mat = [[ 1 , 0 , 0 , 1 , 0 ], [ 0 , 1 , 1 , 1 , 1 ], [ 0 , 0 , 0 , 1 , 0 ], [ 1 , 1 , 1 , 1 , 0 ]]; if (searchForRectangle( 4 , 5 , mat)): print ( "Yes" ); else : print ( "No" ) # This code is contributed by phasing17. |
C#
// C# implementation comes from: // https://github.com/MichaelWehar/FourCornersProblem // Written by Niteesh Kumar and Michael Wehar // References: // [1] F. Mráz, D. Prusa, and M. Wehar. // Two-dimensional Pattern Matching against // Basic Picture Languages. CIAA 2019. // [2] D. Prusa and M. Wehar. Complexity of // Searching for 2 by 2 Submatrices in Boolean // Matrices. DLT 2020. using System; using System.Collections.Generic; class GFG { static bool searchForRectangle( int rows, int cols, int [,] mat) { // Make sure that matrix is non-trivial if (rows < 2 || cols < 2) { return false ; } // Create map int num_of_keys; Dictionary< int , List< int >> adjsList = new Dictionary< int , List< int >>(); if (rows >= cols) { // Row-wise num_of_keys = rows; // Convert each row into List of col indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i, j] == 1) { if (!adjsList.ContainsKey(i)) adjsList[i] = new List< int >(); adjsList[i].Add(j); } } } } else { // Col-wise num_of_keys = cols; // Convert each col into List of row indexes for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { if (mat[i, j] == 1) { if (!adjsList.ContainsKey(i)) adjsList[i] = new List< int >(); adjsList[i].Add(j); } } } } // Search for a rectangle whose four corners are 1's Dictionary<Tuple< int , int >, int > pairs = new Dictionary<Tuple< int , int >, int >(); for ( int i = 0; i < num_of_keys; i++) { List< int > values = adjsList[i]; int size = values.Count; for ( int j = 0; j < size - 1; j++) { for ( int k = j + 1; k < size; k++) { var temp = Tuple.Create(values[j], values[k]); if (!pairs.ContainsKey(temp)) { return true ; } else { pairs[temp] = i; } } } } return false ; } // Driver code public static void Main( string [] args) { int [, ] mat = { { 1, 0, 0, 1, 0 }, { 0, 1, 1, 1, 1 }, { 0, 0, 0, 1, 0 }, { 1, 1, 1, 1, 0 } }; if (searchForRectangle(4, 5, mat)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by phasing17 |
Javascript
// JS implementation comes from: // https://github.com/MichaelWehar/FourCornersProblem // Written by Niteesh Kumar and Michael Wehar // References: // [1] F. Mráz, D. Prusa, and M. Wehar. // Two-dimensional Pattern Matching against // Basic Picture Languages. CIAA 2019. // [2] D. Prusa and M. Wehar. Complexity of // Searching for 2 by 2 Submatrices in Boolean // Matrices. DLT 2020. function searchForRectangle( rows, cols, mat) { // Make sure that matrix is non-trivial if (rows < 2 || cols < 2) { return false ; } // Create map let num_of_keys; let adjsList = {}; if (rows >= cols) { // Row-wise num_of_keys = rows; // Convert each row into vector of col indexes for ( var i = 0; i < rows; i++) { for ( var j = 0; j < cols; j++) { if (mat[i][j]) { if (!adjsList.hasOwnProperty(i)) adjsList[i] = [] adjsList[i].push(j); } } } } else { // Col-wise num_of_keys = cols; // Convert each col into vector of row indexes for ( var i = 0; i < rows; i++) { for ( var j = 0; j < cols; j++) { if (mat[i][j] == 1) { if (!adjsList.hasOwnProperty(j)) adjsList[j] = [] adjsList[j].push(i); } } } } // Search for a rectangle whose four corners are 1's let pairs = {}; for ( var i = 0; i < num_of_keys; i++) { let values = adjsList[i]; let size = values.length for ( var j = 0; j < size - 1; j++) { for ( var k = j + 1; k < size; k++) { let temp = (values[j] + "#" + values[k]); if (pairs.hasOwnProperty(temp)) { return true ; } else { pairs[temp] = i; } } } } return false ; } // Driver code let mat = [[ 1, 0, 0, 1, 0 ], [ 0, 1, 1, 1, 1 ], [ 0, 0, 0, 1, 0 ], [ 1, 1, 1, 1, 0 ]]; if (searchForRectangle(4, 5, mat)) console.log( "Yes" ); else console.log( "No" ) // This code is contributed by phasing17. |
Yes
Time Complexity: O(m*n + p*p*log(p*p)), p=max(n,m).
Auxiliary Space: O(n*m)
Contact Us