# LeetCode 391: Perfect Rectangle

## Problem Restatement

We are given a list of axis-aligned rectangles.

Each rectangle is represented as:

```python
[xi, yi, ai, bi]
```

where:

```text
(xi, yi) is the bottom-left corner
(ai, bi) is the top-right corner
```

We need to return `True` if all small rectangles together form one exact rectangular region.

That means:

1. There must be no gaps.
2. There must be no overlaps.
3. The final union must be one rectangle.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of rectangles |
| Rectangle format | `[x1, y1, x2, y2]` |
| Output | `True` if they form an exact rectangle, otherwise `False` |
| Constraint | `1 <= rectangles.length <= 2 * 10^4` |
| Constraint | `-10^5 <= xi < ai <= 10^5` |
| Constraint | `-10^5 <= yi < bi <= 10^5` |

Example function shape:

```python
def isRectangleCover(rectangles: list[list[int]]) -> bool:
    ...
```

## Examples

Example 1:

```python
rectangles = [
    [1, 1, 3, 3],
    [3, 1, 4, 2],
    [3, 2, 4, 4],
    [1, 3, 2, 4],
    [2, 3, 3, 4],
]
```

These rectangles exactly cover one large rectangle from `(1, 1)` to `(4, 4)`.

There are no gaps and no overlaps.

So the answer is:

```python
True
```

Example 2:

```python
rectangles = [
    [1, 1, 2, 3],
    [1, 3, 2, 4],
    [3, 1, 4, 2],
    [3, 2, 4, 4],
]
```

There is a gap between the left group and the right group.

So the answer is:

```python
False
```

Example 3:

```python
rectangles = [
    [1, 1, 3, 3],
    [3, 1, 4, 2],
    [1, 3, 2, 4],
    [2, 2, 4, 4],
]
```

Some rectangles overlap.

So the answer is:

```python
False
```

## First Thought: Check Every Pair

A direct way is to compare every pair of rectangles.

For each pair, check whether they overlap.

Then also check whether the whole shape has no gaps.

The overlap part alone costs:

```python
O(n^2)
```

because there are many rectangle pairs.

With up to `2 * 10^4` rectangles, this is too slow.

Also, detecting gaps directly is awkward. A gap may be surrounded by many rectangles, so pairwise checks do not naturally prove full coverage.

## Key Insight

A perfect rectangular cover has two strong properties.

First, the total area of all small rectangles must equal the area of the bounding rectangle.

Second, the corner behavior must match a perfect cover.

For a perfect cover:

1. The four outer corners appear exactly once.
2. Every internal corner appears an even number of times and cancels out.

A clean way to express this is with a set.

For every small rectangle, toggle its four corners:

```python
(x1, y1)
(x1, y2)
(x2, y1)
(x2, y2)
```

If a corner appears once, add it to the set.

If it appears again, remove it from the set.

At the end, all internal corners should have canceled out.

Only the four corners of the big bounding rectangle should remain.

## Why Area Is Still Needed

Corner checking alone is not enough.

Some invalid shapes can still leave four outer corners.

Area checking catches gaps and overlaps.

The two conditions together are strong:

| Check | What it catches |
|---|---|
| Area equality | Detects missing or extra covered area |
| Corner parity | Detects wrong boundary shape and internal mismatch |

So the algorithm checks both.

## Algorithm

Initialize:

```python
min_x = infinity
min_y = infinity
max_x = -infinity
max_y = -infinity
area_sum = 0
corners = set()
```

For each rectangle `[x1, y1, x2, y2]`:

1. Add its area to `area_sum`.
2. Update the bounding rectangle:
   - `min_x`
   - `min_y`
   - `max_x`
   - `max_y`
3. Toggle its four corners in the set.

After processing all rectangles:

1. Compute the bounding rectangle area.
2. Check that `area_sum` equals the bounding rectangle area.
3. Check that the corner set contains exactly four points.
4. Check that those four points are exactly the bounding rectangle corners.

## Correctness

The bounding rectangle of any exact cover must use the smallest left coordinate, smallest bottom coordinate, largest right coordinate, and largest top coordinate among all small rectangles.

So if the rectangles form an exact cover, the final large rectangle must be:

```python
(min_x, min_y) to (max_x, max_y)
```

The sum of all small rectangle areas must equal the area of this bounding rectangle. If the sum is smaller, there is a gap. If the sum is larger, there is overlap or extra area.

Now consider corners.

Each small rectangle contributes four corners. In a perfect cover, internal corners are shared by adjacent rectangles. These internal appearances come in pairs or groups of four, so toggling them removes them from the set.

The only corners that do not cancel are the four outer corners of the final rectangle:

```python
(min_x, min_y)
(min_x, max_y)
(max_x, min_y)
(max_x, max_y)
```

Therefore a valid cover must leave exactly these four corners.

Conversely, if the total area equals the bounding rectangle area and the only remaining toggled corners are the four bounding corners, then the union has the same area as the bounding rectangle and the boundary matches one rectangle. There is no room for gaps or overlaps. So the rectangles form an exact cover.

## Complexity

Let `n = len(rectangles)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each rectangle is processed once |
| Space | `O(n)` | The corner set may store many points |

## Implementation

```python
class Solution:
    def isRectangleCover(self, rectangles: list[list[int]]) -> bool:
        min_x = float("inf")
        min_y = float("inf")
        max_x = float("-inf")
        max_y = float("-inf")

        area_sum = 0
        corners = set()

        def toggle(point):
            if point in corners:
                corners.remove(point)
            else:
                corners.add(point)

        for x1, y1, x2, y2 in rectangles:
            area_sum += (x2 - x1) * (y2 - y1)

            min_x = min(min_x, x1)
            min_y = min(min_y, y1)
            max_x = max(max_x, x2)
            max_y = max(max_y, y2)

            toggle((x1, y1))
            toggle((x1, y2))
            toggle((x2, y1))
            toggle((x2, y2))

        bounding_area = (max_x - min_x) * (max_y - min_y)

        expected_corners = {
            (min_x, min_y),
            (min_x, max_y),
            (max_x, min_y),
            (max_x, max_y),
        }

        return area_sum == bounding_area and corners == expected_corners
```

## Code Explanation

We track the bounding rectangle:

```python
min_x = float("inf")
min_y = float("inf")
max_x = float("-inf")
max_y = float("-inf")
```

We also track the total area:

```python
area_sum = 0
```

The set stores corners that appear an odd number of times:

```python
corners = set()
```

The helper function toggles a corner:

```python
def toggle(point):
    if point in corners:
        corners.remove(point)
    else:
        corners.add(point)
```

For each rectangle, add its area:

```python
area_sum += (x2 - x1) * (y2 - y1)
```

Then update the bounding rectangle:

```python
min_x = min(min_x, x1)
min_y = min(min_y, y1)
max_x = max(max_x, x2)
max_y = max(max_y, y2)
```

Then toggle its four corners:

```python
toggle((x1, y1))
toggle((x1, y2))
toggle((x2, y1))
toggle((x2, y2))
```

After all rectangles are processed, compute the area of the bounding rectangle:

```python
bounding_area = (max_x - min_x) * (max_y - min_y)
```

The only allowed remaining corners are:

```python
expected_corners = {
    (min_x, min_y),
    (min_x, max_y),
    (max_x, min_y),
    (max_x, max_y),
}
```

The final condition checks both area and corners:

```python
return area_sum == bounding_area and corners == expected_corners
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.isRectangleCover([
        [1, 1, 3, 3],
        [3, 1, 4, 2],
        [3, 2, 4, 4],
        [1, 3, 2, 4],
        [2, 3, 3, 4],
    ]) is True

    assert s.isRectangleCover([
        [1, 1, 2, 3],
        [1, 3, 2, 4],
        [3, 1, 4, 2],
        [3, 2, 4, 4],
    ]) is False

    assert s.isRectangleCover([
        [1, 1, 3, 3],
        [3, 1, 4, 2],
        [1, 3, 2, 4],
        [2, 2, 4, 4],
    ]) is False

    assert s.isRectangleCover([
        [0, 0, 1, 1],
    ]) is True

    assert s.isRectangleCover([
        [0, 0, 1, 1],
        [1, 0, 2, 1],
        [0, 1, 1, 2],
        [1, 1, 2, 2],
    ]) is True

    assert s.isRectangleCover([
        [0, 0, 2, 1],
        [0, 1, 1, 2],
        [1, 1, 2, 2],
        [0, 0, 1, 2],
    ]) is False

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| Five rectangles exact cover | Main valid example |
| Two separated groups | Detects a gap |
| Overlapping rectangle | Detects overlap |
| Single rectangle | A rectangle covers itself |
| Four unit squares | Simple exact cover |
| Duplicate-covered area | Detects area mismatch from overlap |