LeetCode 391 - Perfect Rectangle

LeetCode Problem 391

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Geometry, Sweep Line

Solution

Problem Understanding

This problem asks whether a collection of smaller axis-aligned rectangles perfectly forms one larger rectangle, with no gaps and no overlaps.

Each rectangle is represented as:

[xi, yi, ai, bi]

where:

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

Because the rectangles are axis-aligned, their sides are parallel to the x-axis and y-axis.

The task is to determine whether all rectangles together create one exact rectangular region. That means:

1. Every point inside the final bounding rectangle must be covered.
2. No point may be covered more than once.
3. There must not be any holes or missing regions.
4. The union of all rectangles must itself be a rectangle.

The input size can be as large as 2 * 10^4 rectangles, so any solution that tries to examine individual unit cells or simulate geometry on a grid is infeasible. Coordinates may also be as large as 10^5 in magnitude, which means coordinate compression or brute-force rasterization would still be too expensive.

The important edge cases include:

• Rectangles that overlap partially
• Rectangles that leave tiny gaps
• Rectangles that touch only at edges or corners
• Duplicate rectangles
• A single rectangle, which should return true
• Complex arrangements where area matches but geometry is still invalid

A naive implementation might only compare total area, but equal area alone is not enough. Two overlapping rectangles can still produce the correct total area if another region is missing. Similarly, checking only boundary coordinates is insufficient because internal overlaps or holes may still exist.

The challenge is detecting both overlaps and gaps efficiently.

Approaches

Brute Force Approach

A brute-force idea is to model the entire 2D plane covered by the rectangles and mark every unit square that gets covered.

For each rectangle:

1. Iterate through all integer coordinate cells it covers.
2. Mark those cells in a hash set or grid.
3. If a cell is visited twice, an overlap exists.
4. After processing all rectangles, verify that the covered cells form one perfect rectangle.

This approach works conceptually because it directly checks every covered region.

However, it is far too slow and memory intensive. Coordinates can be as large as 10^5, meaning the geometric area may be enormous. Even a single rectangle could span billions of unit cells.

Therefore, brute force is not practical.

Key Insight

A perfect rectangle cover has two critical properties:

1. The total area of all small rectangles must equal the area of the final bounding rectangle.
2. Every internal corner appears an even number of times, while the four outer corners appear exactly once.

This second observation is the heart of the optimal solution.

Consider what happens when rectangles fit together perfectly:

• Shared edges cause internal corners to cancel out.
• Only the four corners of the final large rectangle remain unmatched.

We can track corners using a hash set:

• If a corner appears once, add it.
• If it appears again, remove it.

After processing all rectangles:

• Exactly four corners should remain.
• Those corners must be the corners of the bounding rectangle.
• The area must match exactly.

If either condition fails, the rectangles do not form a perfect cover.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(total covered area)	O(total covered area)	Simulates coverage cell by cell, infeasible for large coordinates
Optimal	O(n)	O(n)	Uses area validation and corner parity observation

Algorithm Walkthrough

Optimal Corner Set Algorithm

1. Initialize variables for the bounding rectangle.

Track:

• minimum x
• minimum y
• maximum x
• maximum y

These values define the outer rectangle that should contain everything. 2. Initialize a variable for total area.

As each rectangle is processed, compute:

$\text{area} = (a_i - x_i)(b_i - y_i)$

Add this to the running total. 3. Create a hash set for corners.

Each rectangle contributes four corners:

• (xi, yi)
• (xi, bi)
• (ai, yi)
• (ai, bi)

4. Toggle each corner in the set.

For every corner:

• If the corner is not in the set, insert it.
• If the corner is already present, remove it.

This works because internal corners are shared between rectangles and should appear an even number of times. 5. Update the bounding rectangle.

For every rectangle:

• min_x = min(min_x, xi)
• min_y = min(min_y, yi)
• max_x = max(max_x, ai)
• max_y = max(max_y, bi)

6. After processing all rectangles, verify that exactly four corners remain.

The remaining corners must be:

• (min_x, min_y)
• (min_x, max_y)
• (max_x, min_y)
• (max_x, max_y)

7. Compute the area of the bounding rectangle.

$\text{bounding area} = (\text{max}_x - \text{min}_x)(\text{max}_y - \text{min}_y)$ 8. Compare the areas.

If the total area of all small rectangles differs from the bounding rectangle area, return false. 9. If all checks pass, return true.

Why it works

The algorithm relies on two invariants.

First, a perfect cover cannot have extra or missing area, so the total area must exactly equal the bounding rectangle area.

Second, every internal corner is shared between rectangles and therefore appears an even number of times. Toggling corners removes these internal points. Only the four outer corners remain.

If there is any overlap or gap, at least one of these properties breaks:

• overlaps distort area or corner parity
• gaps distort area or leave extra unmatched corners

Together, these checks are sufficient to guarantee correctness.

Python Solution

from typing import List, Set, Tuple

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")

        total_area = 0
        corners: Set[Tuple[int, int]] = set()

        for x1, y1, x2, y2 in rectangles:
            # Update 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)

            # Add rectangle area
            total_area += (x2 - x1) * (y2 - y1)

            # Rectangle corners
            rectangle_corners = [
                (x1, y1),
                (x1, y2),
                (x2, y1),
                (x2, y2),
            ]

            # Toggle corners in the set
            for corner in rectangle_corners:
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)

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

        # Corner validation
        if corners != expected_corners:
            return False

        # Area validation
        bounding_area = (max_x - min_x) * (max_y - min_y)

        return total_area == bounding_area

The implementation closely follows the algorithm described earlier.

The first section initializes the bounding rectangle coordinates and the total accumulated area.

The corners set is the key data structure. Every time a corner appears, it is toggled in the set. Internal corners eventually cancel out because they appear an even number of times.

For each rectangle:

• the bounding box is updated
• the rectangle area is added
• the four corners are processed

After all rectangles are processed, the code constructs the four expected corners of the final rectangle.

If the remaining corner set differs from these four points, the rectangles do not form a perfect cover.

Finally, the total accumulated area is compared against the bounding rectangle area. If both conditions hold, the answer is True.

Go Solution

package main

func isRectangleCover(rectangles [][]int) bool {
	minX, minY := int(1e9), int(1e9)
	maxX, maxY := -int(1e9), -int(1e9)

	totalArea := 0

	corners := make(map[[2]int]bool)

	for _, rect := range rectangles {
		x1, y1, x2, y2 := rect[0], rect[1], rect[2], rect[3]

		// Update bounding rectangle
		if x1 < minX {
			minX = x1
		}
		if y1 < minY {
			minY = y1
		}
		if x2 > maxX {
			maxX = x2
		}
		if y2 > maxY {
			maxY = y2
		}

		// Add area
		totalArea += (x2 - x1) * (y2 - y1)

		rectCorners := [][2]int{
			{x1, y1},
			{x1, y2},
			{x2, y1},
			{x2, y2},
		}

		// Toggle corners
		for _, corner := range rectCorners {
			if corners[corner] {
				delete(corners, corner)
			} else {
				corners[corner] = true
			}
		}
	}

	expectedCorners := map[[2]int]bool{
		{minX, minY}: true,
		{minX, maxY}: true,
		{maxX, minY}: true,
		{maxX, maxY}: true,
	}

	if len(corners) != 4 {
		return false
	}

	for corner := range expectedCorners {
		if !corners[corner] {
			return false
		}
	}

	boundingArea := (maxX - minX) * (maxY - minY)

	return totalArea == boundingArea
}

The Go implementation mirrors the Python logic almost exactly.

The main difference is that Go does not have a built-in tuple type, so a fixed-size array [2]int is used to represent corner coordinates.

The corner toggling behavior is implemented with a map[[2]int]bool.

Go integers are sufficient for this problem because the maximum possible area remains within the 32-bit signed integer range, although using int64 would also be acceptable for additional safety.

Worked Examples

Example 1

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

Step-by-step processing

Rectangle	Area Added	Corner Set After Processing
[1,1,3,3]	4	{(1,1),(1,3),(3,1),(3,3)}
[3,1,4,2]	1	{(1,1),(1,3),(3,3),(4,1),(4,2),(3,2)}
[3,2,4,4]	2	{(1,1),(1,3),(3,3),(4,1),(4,4),(3,4)}
[1,3,2,4]	1	{(1,1),(3,3),(4,1),(4,4),(3,4),(2,3),(2,4),(1,4)}
[2,3,3,4]	1	{(1,1),(1,4),(4,1),(4,4)}

Final bounding rectangle:

(1,1) to (4,4)

Bounding area:

(4 - 1) * (4 - 1) = 9

Total rectangle area:

4 + 1 + 2 + 1 + 1 = 9

Both checks pass, so the answer is true.

Example 2

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

Bounding rectangle:

(1,1) to (4,4)

Bounding area:

9

Total rectangle area:

2 + 1 + 1 + 2 = 6

The area does not match.

This immediately proves there is a gap.

Answer: false

Example 3

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

Bounding rectangle:

(1,1) to (4,4)

Bounding area:

9

Total rectangle area:

4 + 1 + 1 + 4 = 10

The total area exceeds the bounding area, meaning overlap exists.

Answer: false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each rectangle is processed once
Space	O(n)	The corner set may store up to O(n) unique corners

The algorithm performs constant-time work per rectangle:

• updating bounds
• adding area
• toggling four corners

The hash set operations are average-case O(1), so the total runtime is linear in the number of rectangles.

The space complexity comes from storing corner coordinates in the set. In the worst case, many corners remain unmatched during intermediate processing.

Test Cases

from typing import List

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")

        total_area = 0
        corners = set()

        for x1, y1, x2, y2 in rectangles:
            min_x = min(min_x, x1)
            min_y = min(min_y, y1)
            max_x = max(max_x, x2)
            max_y = max(max_y, y2)

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

            for corner in [
                (x1, y1),
                (x1, y2),
                (x2, y1),
                (x2, y2),
            ]:
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)

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

        if corners != expected:
            return False

        return total_area == (max_x - min_x) * (max_y - min_y)

solution = Solution()

# Perfect rectangle cover
assert solution.isRectangleCover([
    [1,1,3,3],
    [3,1,4,2],
    [3,2,4,4],
    [1,3,2,4],
    [2,3,3,4]
]) == True

# Gap between rectangles
assert solution.isRectangleCover([
    [1,1,2,3],
    [1,3,2,4],
    [3,1,4,2],
    [3,2,4,4]
]) == False

# Overlapping rectangles
assert solution.isRectangleCover([
    [1,1,3,3],
    [3,1,4,2],
    [1,3,2,4],
    [2,2,4,4]
]) == False

# Single rectangle
assert solution.isRectangleCover([
    [0,0,1,1]
]) == True

# Duplicate rectangles causing overlap
assert solution.isRectangleCover([
    [0,0,1,1],
    [0,0,1,1]
]) == False

# Thin vertical strips forming rectangle
assert solution.isRectangleCover([
    [0,0,1,3],
    [1,0,2,3],
    [2,0,3,3]
]) == True

# Missing center piece
assert solution.isRectangleCover([
    [0,0,1,1],
    [1,0,2,1],
    [0,1,1,2]
]) == False

# Negative coordinates
assert solution.isRectangleCover([
    [-1,-1,0,0],
    [0,-1,1,0],
    [-1,0,0,1],
    [0,0,1,1]
]) == True

# T-shaped arrangement, not a rectangle
assert solution.isRectangleCover([
    [0,0,3,1],
    [1,1,2,3]
]) == False

Test Summary

Test	Why
Perfect cover example	Validates correct positive case
Gap example	Ensures missing area is detected
Overlap example	Ensures overlaps are detected
Single rectangle	Smallest valid input
Duplicate rectangles	Tests exact overlap handling
Vertical strips	Tests shared edge cancellation
Missing center piece	Detects internal hole
Negative coordinates	Ensures coordinate sign does not matter
T-shaped arrangement	Ensures final shape must be rectangular

Edge Cases

Overlapping rectangles with matching outer bounds

One tricky scenario occurs when rectangles overlap internally while still producing the same outer bounding rectangle. A naive implementation that only checks corner coordinates could incorrectly accept such cases.

The area check prevents this bug. Overlapping regions are counted multiple times in the total area, making the accumulated area larger than the bounding rectangle area.

Gaps hidden inside the rectangle

Another subtle case is when the outer boundary appears correct but there is a hole somewhere inside the structure.

A pure area check can sometimes fail if overlaps compensate for missing regions elsewhere. The corner parity check catches these invalid internal structures because extra unmatched corners remain in the set.

Shared edges and internal corners

When rectangles perfectly align, many corners are shared between adjacent rectangles. A buggy implementation might accidentally count shared corners incorrectly.

The toggle mechanism elegantly handles this situation. Every internal corner appears an even number of times and cancels out automatically. Only the four true outer corners remain at the end.