#391

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Perfect Rectangle

Determine if given axis-aligned rectangles form a perfect cover using array scanning and hash-based corner counting techniques.

array hash table math geometry line sweep

Problem Statement

You are given an array of rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. Each rectangle's bottom-left corner is (xi, yi) and top-right corner is (ai, bi). Your task is to determine whether these rectangles together exactly form a larger rectangular region without overlaps or gaps.

Return true if the rectangles perfectly cover a rectangular region and false otherwise. For example, rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] should return true, while rectangles that leave gaps or overlap, such as [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]], return false.

Examples

Example 1

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

Output: true

All 5 rectangles together form an exact cover of a rectangular region.

Example 2

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

Output: false

Because there is a gap between the two rectangular regions.

Example 3

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

Output: false

Because two of the rectangles overlap with each other.

Constraints

1 <= rectangles.length <= 2 * 104
rectangles[i].length == 4
-105 <= xi < ai <= 105
-105 <= yi < bi <= 105

Solution Approach

Compute total area and bounding box

Scan all rectangles to calculate the total area and determine the minimum and maximum x and y coordinates. This defines the expected large rectangle and helps verify area consistency with the sum of individual rectangles.

Track corners using a hash set

Use a hash set to add each rectangle's four corners. If a corner already exists, remove it. At the end, only the four extreme corners of the bounding rectangle should remain. Any extra or missing corner indicates an overlap or gap.

Validate area and corner consistency

Compare the sum of individual rectangle areas with the area of the bounding rectangle. If areas match and exactly four corners remain in the set, return true. Otherwise, return false due to overlap or gap detected by the array scanning plus hash lookup.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning all rectangles and managing corners in a hash set, and space complexity is O(n) for storing unique corners in the hash set.

What Interviewers Usually Probe

Candidate correctly identifies using corner counting to detect overlaps and gaps.
Candidate computes bounding box and total area to validate perfect rectangle efficiently.
Candidate leverages hash set operations for quick corner addition/removal to simplify checks.

Common Pitfalls or Variants

Common pitfalls

Failing to handle duplicate corners leads to false positives for overlaps.
Neglecting to check area consistency can miss gaps even when corners match.
Assuming rectangles are sorted; unordered rectangles require proper hash-based corner tracking.

Follow-up variants

Check for perfect square cover instead of general rectangle.
Allow rectangles with floating point coordinates and detect exact cover.
Return coordinates of missing or overlapping areas instead of boolean.

FAQ

What is the main pattern to solve Perfect Rectangle?

The core pattern is array scanning combined with hash lookup to track rectangle corners and detect overlaps or gaps.

How do I detect overlaps when checking for a perfect rectangle?

Use a hash set to add and remove corners. If a corner appears twice, it indicates overlap.

Why do we compare total area of rectangles with the bounding rectangle?

Matching areas ensures there are no gaps; mismatched areas immediately indicate a missing or extra region.

Can rectangles be processed in any order?

Yes, but the hash set ensures corner tracking works regardless of order, maintaining correct overlap and gap detection.

What are common mistakes solving Perfect Rectangle with array scans plus hash lookup?

Ignoring duplicate corners, forgetting area validation, or mismanaging hash set operations often leads to incorrect results.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        area = 0
        minX, minY = rectangles[0][0], rectangles[0][1]
        maxX, maxY = rectangles[0][2], rectangles[0][3]
        cnt = defaultdict(int)

        for r in rectangles:
            area += (r[2] - r[0]) * (r[3] - r[1])

            minX = min(minX, r[0])
            minY = min(minY, r[1])
            maxX = max(maxX, r[2])
            maxY = max(maxY, r[3])

            cnt[(r[0], r[1])] += 1
            cnt[(r[0], r[3])] += 1
            cnt[(r[2], r[3])] += 1
            cnt[(r[2], r[1])] += 1

        if (
            area != (maxX - minX) * (maxY - minY)
            or cnt[(minX, minY)] != 1
            or cnt[(minX, maxY)] != 1
            or cnt[(maxX, maxY)] != 1
            or cnt[(maxX, minY)] != 1
        ):
            return False

        del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, maxY)], cnt[(maxX, minY)]

        return all(c == 2 or c == 4 for c in cnt.values())

Continue Practicing

#149 max points on a line #939 minimum area rectangle #963 minimum area rectangle ii