Perfect Rectangle

Perfect Rectangle asks a deceptively simple geometry question — do these axis-aligned rectangles tile one big rectangle exactly? — and rewards a clever counting trick over any brute-force overlap test.

The slow way first

The literal approach: for every pair of rectangles, test whether they overlap, and separately hunt for gaps by scanning the plane. That is O(n²) just for the overlap check, and finding gaps reliably is fiddly. The coordinates can be large, so we cannot just paint a grid either.

The question to ask: what simple, local fact is true of a perfect tiling that is false of a flawed one? There are two — one about area, one about corners.

The idea: area must match, and only outer corners survive

A perfect cover satisfies two conditions together:

1. Area. The sum of the individual rectangle areas equals the area of their bounding box. If they overlap, the sum is too big; if there is a gap, it is too small.
2. Corners. Toggle every rectangle corner in a set — add it the first time, remove it the second. Interior corners are shared by an even number of rectangles, so they cancel. When you are done, the only corners left appearing an odd number of times must be exactly the four corners of the bounding box.

Both checks are needed: area alone misses a rectangle shifted to overlap one spot and leave another bare (same total area), and corners alone can be fooled by a stray duplicate. Together they are airtight.

Walk through it

Step through the animation. For each rectangle we first add its area, then toggle its four corners one rectangle at a time. R0 contributes area 2 and drops all four of its corners into the empty set. R1 adds another 2 (total 4) — and where the two strips meet, its shared corners (1,0) and (1,2) are already present, so the toggle removes them while (2,0) and (2,2) are added. Only after the pass do we compute the bounding box from the min/max of every coordinate: it is 2×2 (area 4), the summed area is 4, and exactly the four box corners remain.

Pseudocode

area = 0
corners = empty set
for each rectangle (x1, y1, x2, y2):
    area += (x2 - x1) * (y2 - y1)
    for each of its 4 corners p:
        if p already in corners: remove it     # appeared an even number of times
        else: add it                           # appeared an odd number of times
compute bounding box from min/max of all coordinates
if area != bounding-box area: return False     # gap or overlap
return corners == exactly the 4 bounding-box corners

The Python solution

def is_rectangle_cover(rectangles):
    area = 0
    corners = set()
    for x1, y1, x2, y2 in rectangles:
        area += (x2 - x1) * (y2 - y1)
        for p in [(x1, y1), (x2, y2), (x1, y2), (x2, y1)]:
            if p in corners:
                corners.remove(p)
            else:
                corners.add(p)
    xs = [r[0] for r in rectangles] + [r[2] for r in rectangles]
    ys = [r[1] for r in rectangles] + [r[3] for r in rectangles]
    box = (min(xs), min(ys), max(xs), max(ys))
    bx, by, bX, bY = box
    if area != (bX - bx) * (bY - by):
        return False
    return corners == {(bx, by), (bX, bY), (bx, bY), (bX, by)}

• area accumulates the true covered area, counting overlaps twice (which is what catches them).
• corners is a set we toggle: each corner is added on first sight and removed on second, so only odd-count corners remain.
• The bounding box is just the min/max of every x and y across all rectangles.
• Line 11 onward builds those coordinate lists; line 15 is the area check — gap or overlap fails here.
• Line 17 is the corner check: the surviving set must equal exactly the four box corners.

Complexity

We trade O(n) space (the corner set) for a single linear pass. The whole problem collapses into two cheap invariants instead of expensive geometry.

When this pattern shows up

Practice