Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).
Return true if all the rectangles together form an exact cover of a rectangular region.
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 Explanation: 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 Explanation: 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 Explanation: Because two of the rectangles overlap with each other.
Constraints:
1 <= rectangles.length <= 2 * 104rectangles[i].length == 4-105 <= xi < ai <= 105-105 <= yi < bi <= 105The Perfect Rectangle problem asks whether a set of smaller rectangles perfectly forms one larger rectangle without overlaps or gaps. A common strategy combines area verification with corner tracking. First, compute the total area of all rectangles and compare it with the area of the bounding rectangle formed by the extreme coordinates. If the areas differ, the rectangles cannot form a perfect cover.
Next, use a set of corners. Add each rectangle's four corners to the set, removing any corner that appears twice. In a valid configuration, only the four outer corners of the final large rectangle remain. This ensures no overlaps or missing regions exist.
An alternative approach uses a line sweep technique to detect overlapping intervals while scanning vertical edges. This method explicitly checks for conflicts between rectangles but is more complex to implement. The corner-set method typically achieves O(n) time with efficient set operations and O(n) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Area Check + Corner Set | O(n) | O(n) |
| Line Sweep with Active Intervals | O(n log n) | O(n) |
CrioDo
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or variations of it can appear in top technical interviews. It tests geometry reasoning, hashing, and sometimes line sweep techniques, making it valuable for advanced interview preparation.
The most common optimal approach combines total area verification with a corner set. By comparing the combined area of all rectangles with the bounding rectangle and tracking corner appearances, you can detect overlaps or gaps efficiently.
A hash set is typically used to store rectangle corner points. Each corner is added or removed as rectangles are processed, leaving only the four outer corners if the configuration forms a perfect rectangle.
Yes, a line sweep approach can detect overlaps by scanning vertical edges and maintaining active intervals. While effective, it is more complex and usually requires sorting events and balanced structures.