<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:
#     def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        
#         rectangles.sort(key=lambda x: (-x[3], x[0]))
#         rectangles = deque(rectangles)
        
#         def overlaps(rect1, rect2):
#             overlaps_x = min(rect1[2], rect2[2]) - max(rect1[0], rect2[0]) > 0
#             overlaps_y =  min(rect1[3], rect2[3]) - max(rect1[1], rect2[1]) > 0
#             return overlaps_x and overlaps_y
        
#         x_left = min(r[0] for r in rectangles)
#         x_right = max(r[2] for r in rectangles)
        
        
#         def merge_levels(a, b, level_y):
#             i = 0
#             j = 0
#             merged = deque()
#             x = x_left

#             while i < len(a) or j < len(b):
#                 cur_a = None
#                 if i < len(a):
#                     cur_a = a[i]
#                     if cur_a[1] >= level_y:
#                         i += 1
#                         continue
#                 cur_b = None
#                 if j < len(b):
#                     cur_b = b[j]
#                     if cur_b[1] >= level_y:
#                         j += 1
#                         continue

#                 if cur_a is not None and cur_a[0] == x:
#                     x = cur_a[2]
#                     merged.append(cur_a)
#                     i += 1
#                 elif cur_b is not None and cur_b[0] == x:
#                     x = cur_b[2]
#                     merged.append(cur_b)
#                     j += 1
#                 else:
#                     return False
                
#             if x != x_right:
#                 return False
            
#             return merged

#         cur_level = deque()
#         while rectangles:
            
#             next_level = deque()
#             next_level_y = rectangles[0][3]
            
#             # check within next lvl
#             while rectangles and rectangles[0][3] == next_level_y:
#                 if next_level:
#                     if not overlaps(rectangles[0], next_level[-1]):
#                         next_level.append(rectangles.popleft())
#                     else:
#                         return False
#                 else:
#                     next_level.append(rectangles.popleft())
        
            
#             cur_level = merge_levels(cur_level, next_level, next_level_y)

#             if not cur_level:
#                 return False
            
#         return True
            
class Solution(object):
    def isRectangleCover(self, rectangles):
        def recordCorner(point):
            if point in corners:
                corners[point] += 1
            else:
                corners[point] = 1

        corners = {}                                # record all corners 
        L, B, R, T, area = float('inf'), float('inf'), -float('inf'), -float('inf'), 0

        for sub in rectangles:
            L, B, R, T = min(L, sub[0]), min(B, sub[1]), max(R, sub[2]), max(T, sub[3])
            ax, ay, bx, by = sub[:]
            area += (bx-ax)*(by-ay)   # sum up the area of each sub-rectangle
            for px in [(ax, ay), (bx, by), (ax, by), (bx, ay)]: recordCorner(px)

        if area != (T-B)*(R-L): return False        # check the area

        big_four = [(L,B),(R,T),(L,T),(R,B)]

        for bf in big_four:                         # check corners of big rectangle
            if bf not in corners or corners[bf] != 1:
                return False

        for key in corners:                         # check existing "inner" points
            if corners[key]%2 and key not in big_four:
                return False

        return True
    
class Solution(object):
    def isRectangleCover(self, rectangles):
        area = 0
        corners = set()
        a, c = lambda: (X - x) * (Y - y), lambda: {(x, y), (x, Y), (X, y), (X, Y)}
        for x, y, X, Y in rectangles:
            area += a()
            corners ^= c()
        x, y, X, Y = (f(z) for f, z in zip((min, min, max, max), zip(*rectangles)))
        return area == a() and corners == c()
            
22900