Perfect Rectangle
HardPrompt
Approaches
2 approaches with complexity analysis and trade-offs.
This approach treats the vertical edges of the rectangles as events along the x-axis. We sweep a vertical line from left to right, maintaining the set of active rectangles (and their y-intervals) that the sweep line is currently intersecting. At each step, we check if the active y-intervals form a single, contiguous block that matches the height of the overall bounding rectangle.
Algorithm
- Create a list of events. For each rectangle
[x1, y1, x2, y2], add two events: a 'start' event(x1, y1, y2)and an 'end' event(x2, y1, y2). - Sort the events based on their x-coordinate.
- Determine the overall bounding box
(minX, minY, maxX, maxY)by iterating through all rectangles once. - Initialize a sweep line and a data structure to track active y-intervals.
- Iterate through the sorted events. At each x-coordinate, update the active y-intervals.
- Between two consecutive event x-coordinates, verify that the active y-intervals form a single, non-overlapping segment that spans from
minYtomaxY. - If this condition holds for the entire sweep from
minXtomaxX, the rectangles form a perfect cover.
Walkthrough
The core idea is to process the rectangles' boundaries in sorted order of their x-coordinates.
-
Event Creation: For each rectangle
[x1, y1, x2, y2], we generate two events: a 'start' event atx1for the interval[y1, y2], and an 'end' event atx2for the same interval. These events are stored in a list. -
Sorting: The list of events is sorted primarily by the x-coordinate. This creates a timeline of when rectangles begin and end as we move from left to right.
-
Sweep and Verify: We iterate through the sorted events. We maintain a data structure (like a sorted list or a balanced tree) of the active y-intervals currently intersected by our sweep line.
- Between any two consecutive x-coordinates from our event list, the set of active y-intervals must be stable. We check if these intervals are perfectly stitched together (no gaps, no overlaps) and if their total length equals the height of the final bounding box (
maxY - minY). - When the sweep line hits an x-coordinate with events:
- For 'start' events, we add their y-intervals to our active set.
- For 'end' events, we remove their y-intervals.
- Between any two consecutive x-coordinates from our event list, the set of active y-intervals must be stable. We check if these intervals are perfectly stitched together (no gaps, no overlaps) and if their total length equals the height of the final bounding box (
-
Bounding Box: Before starting the sweep, we first iterate through all rectangles to find the overall bounding box (
minX,minY,maxX,maxY). This is needed to know the target height (maxY - minY) for our sweep-line checks.
If at any point the check for a perfect vertical segment fails, we can immediately return false. If the sweep completes successfully, it means the rectangles form a perfect cover.
// Note: A full implementation of a sweep-line algorithm is complex.// The following is a conceptual outline demonstrating the logic.import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Map;import java.util.TreeMap; class Solution { public boolean isRectangleCover(int[][] rectangles) { int minX = Integer.MAX_VALUE; int maxX = Integer.MIN_VALUE; // Create events [x, type, y1, y2] where type=1 for start, -1 for end List<int[]> events = new ArrayList<>(); for (int[] r : rectangles) { minX = Math.min(minX, r[0]); maxX = Math.max(maxX, r[2]); events.add(new int[]{r[0], 1, r[1], r[3]}); events.add(new int[]{r[2], -1, r[1], r[3]}); } Collections.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // TreeMap to store the count of active intervals at each y-coordinate TreeMap<Integer, Integer> yCounts = new TreeMap<>(); int i = 0; while (i < events.size()) { int currentX = events.get(i)[0]; // For any x between the bounding box edges, check the active line if (currentX > minX && currentX < maxX) { if (yCounts.size() < 2) return false; // Must have at least a bottom and top int active = 0; int count = 0; for (int val : yCounts.values()) { active += val; if (active == 1) count++; // Segment where one rectangle is active else if (active != 0) return false; // Overlap or other issue } if (count != 1) return false; // Must be one contiguous block } // Process all events at the current x-coordinate int j = i; while (j < events.size() && events.get(j)[0] == currentX) { int[] event = events.get(j); int type = event[1]; int y1 = event[2]; int y2 = event[3]; yCounts.put(y1, yCounts.getOrDefault(y1, 0) + type); if (yCounts.get(y1) == 0) yCounts.remove(y1); yCounts.put(y2, yCounts.getOrDefault(y2, 0) - type); if (yCounts.get(y2) == 0) yCounts.remove(y2); j++; } i = j; } return true; }}Complexity
Time
O(N log N), where N is the number of rectangles. The dominant operation is sorting the 2N events. Processing each event can be done in O(log N) or O(1) depending on the data structure used for the sweep line.
Space
O(N) to store the 2N events and the data structure for the active y-intervals.
Trade-offs
Pros
A standard and powerful technique for a wide range of computational geometry problems.
Can be adapted to solve similar problems involving intervals or shapes.
Cons
Significantly more complex to implement correctly compared to the point-counting method.
The logic for managing the active intervals and checking for perfect coverage at each step is non-trivial and error-prone.
Can be less efficient due to the sorting step and the complexity of operations on the interval data structure.
Solutions
Solution
class Solution {public boolean isRectangleCover(int[][] rectangles) { long area = 0; int minX = rectangles[0][0], minY = rectangles[0][1]; int maxX = rectangles[0][2], maxY = rectangles[0][3]; Map<Pair, Integer> cnt = new HashMap<>(); for (int[] r : rectangles) { area += (r[2] - r[0]) * (r[3] - r[1]); minX = Math.min(minX, r[0]); minY = Math.min(minY, r[1]); maxX = Math.max(maxX, r[2]); maxY = Math.max(maxY, r[3]); cnt.merge(new Pair(r[0], r[1]), 1, Integer : : sum); cnt.merge(new Pair(r[0], r[3]), 1, Integer : : sum); cnt.merge(new Pair(r[2], r[3]), 1, Integer : : sum); cnt.merge(new Pair(r[2], r[1]), 1, Integer : : sum); } if (area != (long)(maxX - minX) * (maxY - minY) || cnt.getOrDefault(new Pair(minX, minY), 0) != 1 || cnt.getOrDefault(new Pair(minX, maxY), 0) != 1 || cnt.getOrDefault(new Pair(maxX, maxY), 0) != 1 || cnt.getOrDefault(new Pair(maxX, minY), 0) != 1) { return false; } cnt.remove(new Pair(minX, minY)); cnt.remove(new Pair(minX, maxY)); cnt.remove(new Pair(maxX, maxY)); cnt.remove(new Pair(maxX, minY)); return cnt.values().stream().allMatch(c->c == 2 || c == 4); }private static class Pair { final int first; final int second; Pair(int first, int second) { this.first = first; this.second = second; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Pair pair = (Pair)o; return first == pair.first && second == pair.second; } @Override public int hashCode() { return Objects.hash(first, second); } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.