# Short CPP Solution with Set

Use two Sets to count individual corners. Complexity : O(NlogN).
Got a TLE on Java with the same algorithm using HashSet :(

``````class Solution {
public:
bool isRectangleCover(vector<vector<int>>& r) {
set< pair<int,int> > h,hh;
long long area;
int n = r.size();
int maxint = 2147483647;
int ux = -maxint;
int dx = maxint;
int uy = -maxint;
int dy = maxint;

for (int i=0;i<n;i++)
{
for (int k1=0;k1<=2;k1+=2)
for (int k2=1;k2<=3;k2+=2)
{
pair<int,int> t = make_pair(r[i][k1],r[i][k2]);
if (h.find(t)!=h.end() && hh.find(t)!=hh.end()) hh.erase(hh.find(t));
else
{
h.insert(t);
hh.insert(t);
}
}
ux = max(ux,r[i][2]);
dx = min(dx,r[i][0]);
uy = max(uy,r[i][3]);
dy = min(dy,r[i][1]);
area+=1LL*(r[i][2]-r[i][0])*(r[i][3]-r[i][1]);
}

if (area != 1LL*(ux-dx)*(uy-dy)) return false;
return hh.size()==4;

}
};
``````

• It's wrong, fails for example `[[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[0,0,1,1],[2,2,3,3]]`.

• @StefanPochmann Very nice challenge. I guess the best solution is segment tree+linear scan.

• @StefanPochmann You can simplify the example to [[0,0,1,1],[0,0,1,1],[0,2,1,3]].

• Thanks, added both of you and Stefan's test cases.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.