How to Solve Perfect Rectangle

This problem requires verifying that a set of rectangles forms a perfect rectangle without gaps or overlaps. Start by computing the total area of all rectangles and tracking corners using a hash set. The solution focuses on array scanning plus hash lookup to detect overlaps and ensure only the four extreme corners remain.

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

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.

How GhostInterview Helps

• GhostInterview provides step-by-step corner tracking and area validation using array scans plus hash lookup.
• The tool highlights failure cases such as gaps or overlaps and explains why the hash set approach detects them.
• It guides efficient implementation patterns, ensuring candidates apply array scanning and hash-based validation correctly.

Topic Pages

• Array
• Hash Table
• Math
• Geometry
• Line Sweep

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.