LeetCode 391: Perfect Rectangle

Problem Restatement

We are given a list of axis-aligned rectangles.

Each rectangle is represented as:

[xi, yi, ai, bi]

where:

(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

Example function shape:

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

Examples

Example 1:

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:

True

Example 2:

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:

False

Example 3:

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

Some rectangles overlap.

So the answer is:

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:

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:

(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:

So the algorithm checks both.

Algorithm

Initialize:

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:

(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:

(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).

Implementation

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:

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

We also track the total area:

area_sum = 0

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

corners = set()

The helper function toggles a corner:

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

For each rectangle, add its area:

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

Then update the bounding rectangle:

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:

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

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

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

The only allowed remaining corners are:

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:

return area_sum == bounding_area and corners == expected_corners

Testing

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: