> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Perfect Rectangle Python Solution with Tests

> Tested Python solution for LeetCode 391 with 43 pytest cases. Generate a practice environment with lcpy.

LeetCode 391, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [Math](/catalog/topics/math), [Geometry](/catalog/topics/geometry), Sweep Line. [View on LeetCode](https://leetcode.com/problems/perfect-rectangle/description/).

Generate this problem as a practice environment: tested reference solution, 43 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 391   # by problem number
lcpy gen -s perfect_rectangle   # by problem name
```

## Problem

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

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg)

```
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](https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg)

```
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](https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg)

```
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^4
* rectangles\[i].length == 4
* -10^5 \<= xi \< ai \<= 10^5
* -10^5 \<= yi \< bi \<= 10^5

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/perfect_rectangle/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/perfect_rectangle/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n)
    # Space: O(n)
    def is_rectangle_cover(self, rectangles: list[list[int]]) -> bool:
        area = 0
        corners: set[tuple[int, int]] = set()
        min_x = min_y = 10**9
        max_x = max_y = -(10**9)
        for x, y, a, b in rectangles:
            min_x = min(min_x, x)
            min_y = min(min_y, y)
            max_x = max(max_x, a)
            max_y = max(max_y, b)
            area += (a - x) * (b - y)
            for corner in ((x, y), (a, y), (x, b), (a, b)):
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)
        if area != (max_x - min_x) * (max_y - min_y):
            return False
        return corners == {(min_x, min_y), (max_x, min_y), (min_x, max_y), (max_x, max_y)}
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.