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:

Yes

Time Complexity: O(m² * n²) 
Auxiliary Space: O(1), since no extra space has been taken.

Efficient Approach:

1. Scan from top to down, line by line
2. For each line, remember each combination of 2 1’s and push that into a hash-set
3. If we ever find that combination again in a later line, we get our rectangle

Below is the implementation of the above approach:

Yes

Time Complexity: O(n*m²)
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:

Yes

Time Complexity: O(m*n + p*p*log(p*p)), p=max(n,m).
Auxiliary Space: O(n*m)