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 1.

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

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Brute Force Approach-
We start scanning the matrix whenever we find a 1 at any index then we try for all the combination 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][k]==1 &&
             matrix[l][i]==1 &&
             m[l][k]==1)
                return true
return false

Time Complexity: O(m^2*n^2)

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 conteibuted 
# by mohit kumar 29 

Output:

Yes

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

Time Complexity: O(n*m^2)

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 
            if (table.find(j) != table.end() && 
                table[j].find(k) != table[j].end()) 
                        return true; 
  
            if (table.find(k) != table.end() && 
                table[k].find(j) != table[k].end()) 
                        return true; 
  
            // store the indexes in hashset 
            table[j].insert(k); 
            table[k].insert(j); 
          } 
        } 
      } 
    } 
    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

// 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 

Output:

Yes

Find if there is a rectangle in binary matrix with corners as 1

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

C++

Java

Python3

C++

Java

Python3

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books