LeetCode 391: Perfect Rectangle Solution in Python – A Step-by-Step Guide

What Is LeetCode 391: Perfect Rectangle?

LeetCode 391: Perfect Rectangle provides a list of rectangles, each defined by bottom-left and top-right coordinates [x1, y1, x2, y2]. Your task is to check if they form a perfect larger rectangle when combined, with no gaps or overlaps beyond the boundary. It’s a problem that tests your ability to validate geometric consistency efficiently!

Problem Statement

• Input:
• rectangles: List of [x1, y1, x2, y2] representing rectangles.
• Output: Boolean - True if they form a perfect rectangle, False otherwise.
• Rules:
• Each rectangle is [bottom-left x, bottom-left y, top-right x, top-right y].
• Perfect rectangle means total area equals sum of individual areas, no gaps/overlaps.
• Coordinates are integers.

Constraints

• 1 <= rectangles.length <= 2000
• 0 <= xi, yi <= 10⁹
• Rectangle sides > 0.

Examples

• Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
• Output: True
• Forms a 3x3 rectangle at [1,1,4,4].
• Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
• Output: False
• Gap at [2,2,3,3].
• Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,2,2,4]]
• Output: False
• Overlap at [1,2,2,3].

These show the perfect fit puzzle—let’s solve it!

Understanding the Problem: Verifying a Perfect Rectangle

To tackle LeetCode 391 in Python, we need to: 1. Verify all rectangles together form a single larger rectangle. 2. Ensure no gaps or overlaps within the boundary. 3. Check efficiently given up to 2000 rectangles.

A naive approach might check every point, but that’s O(n * area). We’ll use:

• Best Solution: Corner counting and area check—O(n) time, O(n) space—fast and elegant.
• Alternative Solution: Sweep line—O(n log n) time, O(n) space—intuitive but slower.

Let’s verify with the best solution!

Best Solution: Corner Counting and Area Check

Why This Is the Best Solution

The corner counting and area check approach runs in O(n) time with O(n) space by:

• Checking total area matches the bounding rectangle’s area.
• Ensuring all corner points appear an even number of times (2 or 4), except the four outer corners (appear once).

It’s the most efficient—using geometric properties to validate in one pass without complex sorting!

How It Works

Think of it like a jigsaw puzzle:

• Area Check: Sum individual areas = area of bounding rectangle (no gaps/overlaps).
• Corners:
• Each rectangle has 4 corners: (x1,y1), (x1,y2), (x2,y1), (x2,y2).
• Inner corners cancel (appear 2 or 4 times), outer corners remain (appear once).
• Process:
• Track min/max x,y for bounding rectangle.
• Count corner occurrences in a set.
• Verify: 4 outer corners appear once, total area matches.
• Result: True if conditions met, False otherwise.

It’s like ensuring all pieces fit perfectly!

Step-by-Step Example

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

• Area:
• [1,1,3,3]: 4, [3,1,4,2]: 1, [3,2,4,4]: 2, [1,3,2,4]: 1, [2,3,3,4]: 1.
• Sum = 9.
• Bounding Rect:
• Min x=1, Max x=4, Min y=1, Max y=4 → Area = 3 * 3 = 9.
• Corners:
• (1,1): 1, (1,3): 2, (2,3): 2, (2,4): 1, (3,1): 2, (3,2): 2, (3,3): 2, (3,4): 2, (4,1): 1, (4,2): 2, (4,4): 1.
• Count 1: (1,1), (2,4), (4,1), (4,4) → 4 outer corners.
• Check: Area matches (9=9), 4 corners with count 1, return True.

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

• Area: Sum = 6, Bounding = 3 * 3 = 9 → Mismatch, return False.

Code with Explanation

Here’s the Python code using corner counting:

Copy codeclass Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        # Track bounding rectangle corners and area
        min_x = float('inf')
        min_y = float('inf')
        max_x = float('-inf')
        max_y = float('-inf')
        total_area = 0
        corners = set()

        # Process each rectangle
        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)

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

            # Track corners (toggle presence)
            c1 = (x1, y1)
            c2 = (x1, y2)
            c3 = (x2, y1)
            c4 = (x2, y2)
            for corner in (c1, c2, c3, c4):
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)

        # Check area matches bounding rectangle
        if total_area != (max_x - min_x) * (max_y - min_y):
            return False

        # Check exactly 4 corners remain (outer corners)
        if len(corners) != 4:
            return False

        # Verify corners match bounding rectangle
        expected = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
        return corners == expected

Explanation

• Lines 4-9: Initialize bounding coords, area, and corner set—O(1).
• Lines 11-27: Process rectangles:
• Update min/max coords—O(1).
• Add area—O(1).
• Toggle corners in set (add/remove)—O(1).
• Lines 29-35: Validate:
• Area check—O(1).
• Corner count (4)—O(1).
• Corner match—O(1).
• Time: O(n)—single pass, O(1) per rectangle.
• Space: O(n)—corner set (bounded by n).

This is like a geometric validator—fast and precise!

Alternative Solution: Sweep Line

Why an Alternative Approach?

The sweep line solution runs in O(n log n) time with O(n) space by sorting events (rectangle edges) and sweeping left-to-right, tracking active segments to detect overlaps or gaps. It’s more complex—great for understanding a classic geometric algorithm, though slower than corner counting!

How It Works

• Events: Create start/stop events for each rectangle.
• Sort: Sort events by x-coordinate.
• Sweep: Track active y-segments, check for continuity and overlaps.
• Result: True if no gaps/overlaps, area matches.

Step-by-Step Example

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

• Events:
• Start: (1, 1-3, True), (3, 1-2, True).
• End: (3, 1-3, False), (4, 1-2, False).
• Sort: [(1, 1-3, T), (3, 1-3, F), (3, 1-2, T), (4, 1-2, F)].
• Sweep:
• x=1: Add 1-3, Active = [(1,3)].
• x=3: Remove 1-3, Add 1-2, Active = [(1,2)] (gap at 2-3).
• Result: False (gap detected).

Code with Explanation

Copy codefrom collections import defaultdict

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        # Events: (x, y1-y2, is_start)
        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append((x1, (y1, y2), True))
            events.append((x2, (y1, y2), False))
        events.sort()  # Sort by x

        # Track active segments
        active = []
        total_area = 0
        min_y = float('inf')
        max_y = float('-inf')

        # Sweep line
        prev_x = events[0][0]
        for x, (y1, y2), is_start in events:
            # Calculate area between x-coordinates
            if active and x > prev_x:
                curr_height = 0
                prev_y = None
                for ay1, ay2 in sorted(active):
                    if prev_y is None or ay1 > prev_y:
                        curr_height += ay2 - ay1
                    elif ay2 > prev_y:
                        curr_height += ay2 - prev_y
                    prev_y = max(prev_y, ay2) if prev_y else ay2
                total_area += curr_height * (x - prev_x)

            # Update active segments
            if is_start:
                active.append((y1, y2))
            else:
                active.remove((y1, y2))

            prev_x = x

        # Check total area and bounding rectangle
        bounding_area = (max(rect[2] for rect in rectangles) - min(rect[0] for rect in rectangles)) * \
                        (max(rect[3] for rect in rectangles) - min(rect[1] for rect in rectangles))
        return total_area == sum((x2-x1)*(y2-y1) for x1, y1, x2, y2 in rectangles) and total_area == bounding_area

Explanation

• Lines 6-9: Create start/stop events—O(n).
• Line 10: Sort events by x—O(n log n).
• Lines 12-37: Sweep:
• Compute area between x’s—O(n log n) with sorting active.
• Add/remove segments—O(n).
• Lines 39-41: Verify areas match—O(n).
• Time: O(n log n)—sorting dominates.
• Space: O(n)—active list.

It’s a geometric sweeper—detailed but slower!

Comparing the Two Solutions

• Corner Counting (Best):
• Time: O(n)—linear.
• Space: O(n)—corners.
• Pros: Fast, simple, scalable.
• Cons: Less visual.
• Sweep Line (Alternative):
• Time: O(n log n)—sorting.
• Space: O(n)—active segments.
• Pros: Classic algorithm.
• Cons: Slower, complex.

Corner counting wins for speed and simplicity!

Additional Examples and Edge Cases

• Single rect: Both return True.
• Overlap: Both detect False.
• Large n: Corner counting scales better.

Corner counting is optimal, sweep line works too.

Complexity Breakdown

• Corner Counting:
• Time: O(n).
• Space: O(n).
• Sweep Line:
• Time: O(n log n).
• Space: O(n).

Corner counting excels for efficiency.

Key Takeaways

• Corner Counting: Check fit—fast and lean!
• Sweep Line: Scan fit—clear but slow!
• Geometry: Patterns beat simulation.
• Python Tip: Sets rock—see [Python Basics](/python/basics).

Final Thoughts: Verify That Fit

LeetCode 391: Perfect Rectangle in Python is a geometric challenge. Corner counting is the efficiency champ, while sweep line offers a detailed alternative. Want more? Try LeetCode 223: Rectangle Area or LeetCode 84: Largest Rectangle in Histogram. Ready to tile? Visit Solve LeetCode 391 on LeetCode and check that rectangle today!