-
Notifications
You must be signed in to change notification settings - Fork 2
/
Find rectangle with corners as 1.cpp
27 lines (25 loc) · 1.11 KB
/
Find rectangle with corners as 1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
Given a NxM binary matrix consisting of 0s and 1s.
Find if there exists a rectangle/ square within the matrix whose all four corners are 1.
*/
bool ValidCorner(const vector<vector<int> >& matrix)
{
// Your code goes here
int m = matrix.size();
int n = matrix[0].size();
unordered_map<int,unordered_set<int>> temp;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
for(int k = j+1;k<n;k++){
if(matrix[i][j] == 1 and matrix[i][k] == 1){
// we found one pair on that row
// next we have to check if we get any pair in same column and different row
// firstly finding key(first occourence of 1 in the row) , then finding if have the same pair in the set.
if(temp.find(j) != temp.end() and temp[j].find(k) != temp[j].end()) return true;
else temp[j].insert(k); // we are {col,(next occ of 1 in the same row)} => {col,(col+)} pair
}
}
}
}
return false;
}