Problem

Given an array rectangles where rectangles[i] = [x_i, y_i, a_i, b_i] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (x_i, y_i) and the top-right point of it is (a_i, b_i).

Return true if all the rectangles together form an exact cover of a rectangular region.

Example 1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example 3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.

Constraints:

1 <= rectangles.length <= 2 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i, y_i, a_i, b_i <= 10⁵

Solution

Problem Insight:

The combined area of all small rectangles should equal the area of the large rectangle.

Group 8.jpg

The corners of the large rectangle should appear only once, while all other points where rectangles meet should appear an even number of times.

Group 7.jpg

Solution Breakdown:

Initialization:
```
x1, y1 = float('inf'), float('inf')
x2, y2 = float('-inf'), float('-inf')
corners = set()
area = 0
```
- x1, y1: Bottom-left corner of the large rectangle.
- x2, y2: Top-right corner of the large rectangle.
- corners: A set to store the corners of all rectangles.
- area: To store the total area covered by all small rectangles.
Iterate over each rectangle:
```
for rect in rectangles:
```
For each rectangle, the code does the following:

a. Updates the potential corners of the large rectangle:
```
   x1 = min(rect[0], x1)
   y1 = min(rect[1], y1)
   x2 = max(rect[2], x2)
   y2 = max(rect[3], y2)
```
- This updates the minimum values for the bottom-left corner and the maximum values for the top-right corner.
b. Updates the total area:
```
   area += (rect[2] - rect[0]) * (rect[3] - rect[1])
```
- Adds the area of the current rectangle to the total area.
c. Handles the corners of the current rectangle:
```
   for point in [(rect[0], rect[1]), (rect[0], rect[3]), (rect[2], rect[3]), (rect[2], rect[1])]:
       if point in corners:
           corners.remove(point)
       else:
           corners.add(point)
```
- The four corners of the current rectangle are created as tuples.
- The loop checks each corner:
  - If the corner is already in the corners set, it is removed.
  - If it’s not, it’s added to the set.
- This ensures that corners appearing twice are eliminated from the set.
Final Checks:

a. Check the four corners of the large rectangle:
```
   if {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} != corners:
       return False
```
- This checks if the set contains only the four corners of the large rectangle. If there are other corners left in the set, or if any of these four corners are missing, it returns False.
b. Check the area:
```
   return area == (x2 - x1) * (y2 - y1)
```
- Ensures that the combined area of all small rectangles equals the area of the large rectangle.

Summary:

In this Python solution, we utilize the properties of sets and the efficiency and clarity of tuples to determine if the given rectangles can form a large rectangle without overlaps or gaps. The logic is similar to the Java solution, but the use of tuples makes the code more concise and readable.

Code

class Solution:
  def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
    if not rectangles:
      return False

    x1, y1 = float('inf'), float('inf')
    x2, y2 = float('-inf'), float('-inf')
    corners = set()
    area = 0

    for rect in rectangles:
      x1 = min(rect[0], x1)
      y1 = min(rect[1], y1)
      x2 = max(rect[2], x2)
      y2 = max(rect[3], y2)
      
      area += (rect[2] - rect[0]) * (rect[3] - rect[1])
      
      for point in [(rect[0], rect[1]), (rect[0], rect[3]), (rect[2], rect[3]), (rect[2], rect[1])]:
        if point in corners:
          corners.remove(point)
        else:
          corners.add(point)

    if {(x1, y1), (x1, y2), (x2, y1), (x2, y2)} != corners:
      return False

    return area == (x2 - x1) * (y2 - y1)

Time Complexity:

Iterating over each rectangle:
```
for rect in rectangles:
```
This loop iterates n times, where n is the number of rectangles. Within this loop:

a. Updating the potential corners of the large rectangle and the total area: These operations are (O(1)) for each rectangle.

b. Handling the corners of the current rectangle:
```
   for point in [(rect[0], rect[1]), (rect[0], rect[3]), (rect[2], rect[3]), (rect[2], rect[1])]:
```
This loop iterates 4 times (a constant time). Inside this loop, adding a point to a set or removing a point from a set are both (O(1)) operations.

Thus, the operations inside the main loop are (O(1)), making the overall time complexity of the main loop (O(n)).
Final Checks: Checking the four corners of the large rectangle and checking the area are both (O(1)) operations.

Combining the above, the overall time complexity is (O(n)).

Space Complexity:

Storing the corners:
```
corners = set()
```
In the worst case, if every rectangle is disjoint from the others, there would be 4 corners for each rectangle, so the space required would be (O(4n)) or (O(n)).
Other variables: x1, x2, y1, y2, and area all occupy constant space, (O(1)).

Thus, the overall space complexity is (O(n)).

In conclusion, both the time complexity and the space complexity of the Python solution are (O(n)).

Acknowledgements

Thanks to hu19 for his solution :)