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.
In this approach, we implement a sweep line algorithm combined with an active set of rectangles. This idea is based on checking the vertical lines on the plane where the rectangles are placed. We'll sort the events by x-coordinates and then process them in order:
This Python implementation sorts events of rectangles, where each rectangle contributes two events at its x-bounds. A sorted dictionary manages active y-ranges that are currently being traversed by these sweep lines. We ensure at every point between these x-boundary events that the y-ranges are contiguous and non-overlapping by updating the current_y total and comparing it to the expected area of the bounding rectangle.
Python
JavaScript
Time Complexity: O(n log n), where n is the number of rectangles due to sorting events.
Space Complexity: O(n), where n is the number of active y-intervals stored at any time.
This approach involves tracking the contribution of every rectangle's corners and the total area. By using a set to track seen corners, we can ensure that each corner appears an even number of times, except the four corners of the bounding rectangle, which should appear exactly once.
This Java solution calculates the bounding corners of the rectangles and keeps track of seen corners with a set. After all rectangles are processed, it checks if only the bounding rectangle’s corners are in the set. It compares the net area of smaller rectangles to the area expected from the bounding rectangle.
Time Complexity: O(n), where n is the number of rectangles since we traverse all the rectangles once.
Space Complexity: O(n), due to the set storing rectangle corner points.
| Approach | Complexity |
|---|---|
| Approach 1 - Use a Sweep Line Algorithm | Time Complexity: O(n log n), where n is the number of rectangles due to sorting events. |
| Approach 2 - Use of Set for Corner Tracking | Time Complexity: O(n), where n is the number of rectangles since we traverse all the rectangles once. |
| Default Approach | — |
| 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 |
391. Perfect Rectangle (Leetcode Hard) • Programming Live with Larry • 3,988 views views
Watch 9 more video solutions →Practice Perfect Rectangle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor