AlgoMaster Logo

Perfect Rectangle

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We're given a collection of axis-aligned rectangles, each defined by its bottom-left and top-right corners. The task is to decide whether they tile one large rectangle exactly: every point of some rectangular region covered, and no point covered twice.

Two defects can break a cover. Rectangles can overlap, counting some area twice, or the arrangement can leave gaps, points inside the bounding rectangle that no piece covers.

A perfect cover must pass an area test: the areas of the pieces must sum to the area of the bounding rectangle (the smallest rectangle containing all of them). That test alone cannot decide the problem, because an overlap in one place and an equally sized gap somewhere else produce the same total. Each approach below pairs the area check with a second check that verifies the geometry.

Key Constraints:

  • 1 <= rectangles.length <= 2 * 10^4 → With up to 20,000 rectangles, we can afford O(n log n) or O(n) solutions. An O(n^2) approach that checks every pair for overlap (which would be ~200 million pairs) is borderline and likely too slow given the constant factors.
  • -10^5 <= xi, yi, ai, bi <= 10^5 → Coordinates range from -100,000 to 100,000. This is a manageable range but too large for a 2D grid approach (a grid of 200,000 x 200,000 would be 40 billion cells). It also dictates the arithmetic: a single rectangle can have area up to 4 * 10^10, which overflows a 32-bit integer, so the area sums use 64-bit values.

Approach 1: Brute Force (Area Check + Pairwise Overlap Detection)

Intuition

Test the two failure modes separately. First, compute the bounding rectangle by taking the minimum of all bottom-left coordinates and the maximum of all top-right coordinates, and confirm that the total area of the small rectangles equals the bounding rectangle's area. Second, check that no two rectangles overlap.

Together these two checks are sufficient. Disjoint rectangles have a union whose area equals the sum of their areas. If that sum also equals the bounding rectangle's area, the union is a subset of the bounding rectangle with the same area, so it fills the bounding rectangle completely and the cover is exact.

To check if two axis-aligned rectangles overlap, we use the standard intersection test: two rectangles overlap if and only if one starts before the other ends in both the x and y dimensions. Specifically, rectangles [x1, y1, a1, b1] and [x2, y2, a2, b2] overlap if x1 < a2 && x2 < a1 && y1 < b2 && y2 < b1.

Algorithm

  1. Find the bounding rectangle by tracking the global minimum of all xi, yi and the global maximum of all ai, bi.
  2. Compute the total area by summing (ai - xi) * (bi - yi) for each rectangle.
  3. Compare the total area to the bounding rectangle area. If they differ, return false.
  4. For every pair of rectangles, check if they overlap. If any pair overlaps, return false.
  5. If both checks pass, return true.

Example Walkthrough

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] (Example 1, a valid cover of the square from (1,1) to (4,4)).

1R0 = (1,1)-(3,3): area 4, running total 4. Bounds so far: (1,1)-(3,3)
0
1
2
3
0
1
1
3
3
1
3
1
4
2
2
3
2
4
4
3
1
3
2
4
4
2
3
3
4
1/11

Code

Both checks in the brute force are correct; only the pairwise scan is expensive. The next approach sorts the rectangle edges and turns overlap detection into a one-dimensional problem.

Approach 2: Sweep Line Over Rectangle Edges

Intuition

The brute force compares every pair of rectangles, including pairs that are nowhere near each other. Two rectangles can only overlap if their x-spans intersect, so it is enough to compare each rectangle against the rectangles a vertical line would cut through at the same time. A sweep line organizes the work this way: move a vertical line from left to right and maintain the set of rectangles it currently intersects.

Each rectangle produces two events. Its left edge opens the y-interval [y1, y2) and its right edge closes it. Events are processed in increasing x order, with right edges before left edges at the same x, so that a rectangle ending exactly where another begins does not register as an overlap.

As long as no overlap has been found, the active y-intervals are pairwise disjoint, so they can be kept in a list sorted by start. When a new interval [s, t) opens, only two existing intervals can conflict with it: the one with the greatest start at most s (a conflict if it extends past s) and the one with the smallest start greater than s (a conflict if it starts before t). Every other active interval lies entirely below the first or entirely above the second, because in a disjoint sorted list each interval ends no later than the next one starts. A single binary search locates both neighbors.

The sweep detects overlaps only; a gap leaves no trace in the active set. The area check from Approach 1 stays, and the same argument applies: matching areas plus pairwise-disjoint rectangles mean the cover is exact.

Algorithm

  1. In one pass, compute the bounding rectangle and the total area. If the total area differs from the bounding area, return false.
  2. For each rectangle [x1, y1, x2, y2], create an open event at x1 and a close event at x2, both carrying the y-interval [y1, y2). Sort all 2n events by x, with close events before open events at the same x.
  3. Maintain a list of active y-intervals sorted by start. For each event with interval [s, t), binary search for the position of the first active interval whose start is greater than s.
  4. For an open event: the interval just before that position overlaps [s, t) if it ends after s, and the interval at that position overlaps if it starts before t. If either holds, return false. Otherwise insert [s, t) at that position.
  5. For a close event: remove the interval starting at s, which sits immediately before the searched position.
  6. If every event processes without a conflict, the rectangles are pairwise disjoint and the areas already matched, so return true.

Example Walkthrough

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] (Example 1 again). The area check passes (9 = 9), so the sweep only has to rule out overlaps.

1Total area 9 equals bounding area 9. Build 10 edge events and sort by x, right edges before left edges at equal x
0
1
2
3
0
1
1
3
3
1
3
1
4
2
2
3
2
4
4
3
1
3
2
4
4
2
3
3
4
1/8

For an input that overlaps, such as [[0,0,2,1],[0,1,2,2],[1,1,3,2]], the sweep opens [1,2) for the second rectangle at x=0 and then tries to open [1,2) for the third rectangle at x=1. The left neighbor of the insertion point is the already-active [1,2), which ends after 1, so the function returns false.

Code

The sweep cannot beat its sort. The final approach drops the interval bookkeeping entirely and answers the same question in one pass with a hash set of corner points.

Approach 3: Corner Counting with Area Check (Optimal)

Intuition

Every rectangle contributes four corner points, and a perfect cover forces a strict pattern on how often each point appears. A corner point in the interior of the cover is always shared: where two rectangles meet along an edge, the shared corners appear twice, and where four rectangles meet at a point, it appears four times. The four corners of the bounding rectangle belong to exactly one small rectangle each, so they appear exactly once.

This pattern can be tested with no geometry at all. For each rectangle, toggle its four corners in a hash set: insert a point on its first appearance, remove it on the next, and so on. Points that appear an even number of times cancel out. A perfect cover leaves exactly four surviving points, and they must be the bounding rectangle's corners.

The area check still runs alongside, because corner cancellation alone cannot distinguish coincident rectangles from a clean tiling.

Algorithm

  1. Initialize variables to track the bounding rectangle (minX, minY, maxA, maxB) and total area.
  2. Create an empty set to track corner points that appear an odd number of times.
  3. For each rectangle: update the bounding rectangle coordinates, add its area to the running total, and toggle each of its four corners in the set.
  4. Check that the total area equals the bounding rectangle area. If not, return false.
  5. Check that the set contains exactly 4 points matching the bounding rectangle's corners. If not, return false.
  6. Return true.

Example Walkthrough

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] (Example 1).

1R0 (1,1)-(3,3): all four corners are new. Set: (1,1) (1,3) (3,1) (3,3). Area total 4
0
1
2
3
0
1
1
3
3
1
3
1
4
2
2
3
2
4
4
3
1
3
2
4
4
2
3
3
4
1/7

A failing input shows why both checks matter. For rectangles = [[0,0,2,1],[0,1,2,2],[1,1,3,2]], the bounding rectangle is (0,0)-(3,2) with area 6, and the pieces sum to 2 + 2 + 2 = 6, so the area check passes even though the second and third rectangles overlap on the square (1,1)-(2,2) and the region (2,0)-(3,1) is uncovered. The corner check catches it: after all toggles the set holds eight points, including survivors like (1,1) and (1,2) that are neither cancelled nor bounding corners, so the function returns false.

Code