Leetcode 391 Solution

https://leetcode.com/problems/perfect-rectangle

Solution

``````class Solution {
unordered_map<uint64_t, int> m;

public:
bool isvalid(int x, int y, int flag)
{
auto pt = ((uint64_t)x << 32) + (uint64_t)y;
auto& val = m[pt];
if (val & flag)
return false;

val |= flag;
return true;
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
int min_x = INT_MAX;
int min_y = INT_MAX;
int max_x = INT_MIN;
int max_y = INT_MIN;
int64_t area = 0;

for (auto rect : rectangles)
{
min_x = min(min_x, rect[0]);
min_y = min(min_y, rect[1]);
max_x = max(max_x, rect[2]);
max_y = max(max_y, rect[3]);

if (isvalid(rect[0], rect[1], 1) == false)
return false;

if (isvalid(rect[0], rect[3], 2) == false)
return false;

if (isvalid(rect[2], rect[3], 4) == false)
return false;

if (isvalid(rect[2], rect[1], 8) == false)
return false;

area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
}

int cnt = 0;

for (auto pair : m)
{
int val = pair.second;

if (val == 1 || val == 2 || val == 4 || val == 8)
cnt++;
else if (val != 15 && val != 12 && val != 10 && val != 9 && val != 6 && val != 5 && val != 3)
return false;
}

return cnt == 4 && area == (max_x - min_x) * (max_y - min_y);
}
};
``````