<p>Given an array <code>rectangles</code> where <code>rectangles[i] = [x<sub>i</sub>, y<sub>i</sub>, a<sub>i</sub>, b<sub>i</sub>]</code> represents an axis-aligned rectangle. The bottom-left point of the rectangle is <code>(x<sub>i</sub>, y<sub>i</sub>)</code> and the top-right point of it is <code>(a<sub>i</sub>, b<sub>i</sub>)</code>.</p>

<p>Return <code>true</code> <em>if all the rectangles together form an exact cover of a rectangular region</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
<strong>Output:</strong> true
<strong>Explanation:</strong> All 5 rectangles together form an exact cover of a rectangular region.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because there is a gap between the two rectangular regions.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
<strong>Output:</strong> false
<strong>Explanation:</strong> Because two of the rectangles overlap with each other.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>rectangles[i].length == 4</code></li>
	<li><code>-10<sup>5</sup> &lt;= x<sub>i</sub> &lt; a<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= y<sub>i</sub> &lt; b<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    queue<pair<int,int>> q;
    vector<bool> visited;
    long long area, min_x, min_y, max_x, max_y;
    int check(pair<int,int>& point, map<pair<int,int>, int>& coords, vector<vector<int>>& rectangles ){
        if(coords.count(point)){
            int i = coords[point];
            long long x1=rectangles[i][0], y1=rectangles[i][1], x2=rectangles[i][2], y2=rectangles[i][3];
            if(!visited[i]){
                visited[i] = 1;
                // push all 4 corner indices in the queue
                // add area
                q.push({x1, y2});
                q.push({x2, y2});
                q.push({x1, y1});
                q.push({x2, y1});
                if(x1<min_x || x2>max_x || y1<min_y || y2>max_y){
                    return -1; // Invalid point
                }
                area+=(x2-x1)*(y2-y1);
            }
            return 1;
        }else{
            return 0;
        }
    }
// case: [[0,0,1,1],[0,1,3,2],[1,0,2,2]]
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int n = rectangles.size();
        map<pair<int,int>, int> topLeft, topRight, bottomLeft, bottomRight;
        for(int i=0; i<n; i++){
            int x1=rectangles[i][0], y1=rectangles[i][1], x2=rectangles[i][2], y2=rectangles[i][3];
            if(topLeft.count({x1, y2})) return false;
            topLeft[{x1, y2}] = i;

            if(topRight.count({x2, y2})) return false;
            topRight[{x2, y2}] = i;

            if(bottomLeft.count({x1, y1})) return false;
            bottomLeft[{x1, y1}] = i;

            if(bottomRight.count({x2, y1})) return false;
            bottomRight[{x2, y1}] = i;
        }
        min_x = bottomLeft.begin()->first.first;
        min_y = bottomLeft.begin()->first.second;
        max_x = topRight.rbegin()->first.first;
        max_y = topRight.rbegin()->first.second;
        long long maxArea = (max_x-min_x)*(max_y-min_y);
        // cout<<min_x<<" "<<min_y<<", "<<max_x<<" "<<max_y<<" "<<maxArea<<endl;;
        visited.resize(n);
        q.push({min_x, min_y});

        // bfs
        while(!q.empty()){
            auto curr = q.front();
            q.pop();
            int res1 = check(curr, topLeft, rectangles);
            int res2 = check(curr, topRight, rectangles);
            int res3 = check(curr, bottomLeft, rectangles);
            int res4 = check(curr, bottomRight, rectangles);
            // Invalid point
            if(res1==-1 || res2==-1 || res3==-1 || res3==-1){
                return false;
            }
            // no. of rectangels having corner at point is <=1 and point is not corner of perfect rectangle
            if(res1+res2+res3+res4<=1){
                if(curr!=pair<int,int>{min_x, min_y} 
                    && curr!=pair<int,int>{max_x, min_y} 
                    && curr!=pair<int,int>{min_x, max_y} 
                    && curr!=pair<int,int>{max_x, max_y} ){
                        return false;
                }
            }
        }
        // check if all rectangles has been visited
        for(int i=0; i<n; i++){
            if(!visited[i])return false;
        }

        return area==maxArea;
    }


};
45100