Watch 10 video solutions for Perfect Rectangle, a hard level problem involving Array, Line Sweep. This walkthrough by CrioDo has 304,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105Problem Overview: You receive multiple axis-aligned rectangles defined by their bottom-left and top-right coordinates. The task is to verify whether these rectangles together form one exact larger rectangle with no overlaps and no gaps.
Approach 1: Sweep Line Algorithm (O(n log n) time, O(n) space)
This method treats rectangle edges as events along the x-axis and processes them using a sweep line. Each rectangle contributes two events: a start edge and an end edge. As you sweep from left to right, maintain active vertical intervals in a structure such as a balanced tree or sorted list. When new rectangles start, check whether their y-interval overlaps incorrectly with active intervals; overlaps indicate invalid coverage. When rectangles end, remove their intervals from the active set. Sorting all edge events costs O(n log n), and interval updates during the sweep also take O(log n) each, leading to overall O(n log n) time and O(n) space. This technique is a classic application of line sweep used in computational geometry.
Approach 2: Set-Based Corner Tracking (O(n) time, O(n) space)
The key observation is that in a perfect rectangle cover, every internal corner appears an even number of times while the four outer corners appear exactly once. Iterate through each rectangle and track its four corners in a hash set. Insert a corner if it is not present; remove it if it already exists. After processing all rectangles, only four corners should remain in the set: the corners of the bounding rectangle. Additionally compute the total area of all small rectangles and compare it with the area of the bounding rectangle formed by the extreme coordinates. If the areas match and the corner set contains exactly four expected points, the rectangles form a perfect cover. The algorithm performs constant-time set operations for each corner, giving O(n) time and O(n) space using structures commonly used in array and hashing problems.
Recommended for interviews: Interviewers usually expect the corner tracking solution. It is concise, runs in O(n), and demonstrates recognition of geometric invariants. The sweep line approach shows deeper knowledge of line sweep algorithms and interval management, which is useful in geometry-heavy problems but more complex to implement during a timed interview.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line Algorithm | O(n log n) | O(n) | When solving general rectangle overlap or geometry problems requiring ordered edge processing |
| Corner Set Tracking | O(n) | O(n) | Best choice for interviews and competitive programming due to simple logic and linear time |