Perfect Rectangle

Hard

#0378Time: 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.

Patterns

Line Sweep

Data structures

Array

Prompt

[Fetch error]

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 minY to maxY.
If this condition holds for the entire sweep from minX to maxX, 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 at x1 for the interval [y1, y2], and an 'end' event at x2 for 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.
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.

1// Note: A full implementation of a sweep-line algorithm is complex.2// The following is a conceptual outline demonstrating the logic.3import java.util.ArrayList;4import java.util.Collections;5import java.util.List;6import java.util.Map;7import java.util.TreeMap;8 9class Solution {10    public boolean isRectangleCover(int[][] rectangles) {11        int minX = Integer.MAX_VALUE;12        int maxX = Integer.MIN_VALUE;13 14        // Create events [x, type, y1, y2] where type=1 for start, -1 for end15        List<int[]> events = new ArrayList<>();16        for (int[] r : rectangles) {17            minX = Math.min(minX, r[0]);18            maxX = Math.max(maxX, r[2]);19            events.add(new int[]{r[0], 1, r[1], r[3]});20            events.add(new int[]{r[2], -1, r[1], r[3]});21        }22        Collections.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);23 24        // TreeMap to store the count of active intervals at each y-coordinate25        TreeMap<Integer, Integer> yCounts = new TreeMap<>();26        int i = 0;27        while (i < events.size()) {28            int currentX = events.get(i)[0];29            30            // For any x between the bounding box edges, check the active line31            if (currentX > minX && currentX < maxX) {32                if (yCounts.size() < 2) return false; // Must have at least a bottom and top33                int active = 0;34                int count = 0;35                for (int val : yCounts.values()) {36                    active += val;37                    if (active == 1) count++; // Segment where one rectangle is active38                    else if (active != 0) return false; // Overlap or other issue39                }40                if (count != 1) return false; // Must be one contiguous block41            }42 43            // Process all events at the current x-coordinate44            int j = i;45            while (j < events.size() && events.get(j)[0] == currentX) {46                int[] event = events.get(j);47                int type = event[1];48                int y1 = event[2];49                int y2 = event[3];50                yCounts.put(y1, yCounts.getOrDefault(y1, 0) + type);51                if (yCounts.get(y1) == 0) yCounts.remove(y1);52                yCounts.put(y2, yCounts.getOrDefault(y2, 0) - type);53                if (yCounts.get(y2) == 0) yCounts.remove(y2);54                j++;55            }56            i = j;57        }58 59        return true;60    }61}

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.

This highly efficient approach is based on a simple geometric insight. For a set of non-overlapping rectangles to form a single larger rectangle, two conditions must be met:

The sum of the areas of the small rectangles must equal the area of the bounding box that encloses them.
Except for the four corners of the bounding box, all other corners of the small rectangles must appear an even number of times (i.e., they must be shared by an even number of rectangles to 'cancel out').

Algorithm

Initialize totalArea = 0, bounding box coordinates to extreme values, and an empty HashSet for corner points.
Iterate through each rectangle [x1, y1, x2, y2]:
- Update the bounding box coordinates (minX, minY, maxX, maxY).
- Add the rectangle's area to totalArea.
- For each of the four corner points, toggle its presence in the HashSet. (If it's present, remove it; if not, add it).
After the loop, calculate the expectedArea from the final bounding box coordinates.
Return true only if totalArea equals expectedArea AND the HashSet contains exactly the four corners of the bounding box.

Walkthrough

The algorithm leverages these two properties for a very efficient check.

Initialization: We need variables to track the total area of all small rectangles and the coordinates of the overall bounding box (minX, minY, maxX, maxY). We also need a data structure to count the occurrences of each corner point. A HashSet is perfect for this: adding a point that already exists will be a no-op, so we can implement a toggle: if a point is in the set, we remove it; otherwise, we add it. At the end, the set will only contain points that appeared an odd number of times.
Iteration: We loop through each rectangle [x1, y1, x2, y2] once:
1. Update minX, minY, maxX, maxY with the coordinates of the current rectangle.
2. Add the area (x2 - x1) * (y2 - y1) to a running total.
3. Process the four corner points: (x1, y1), (x1, y2), (x2, y1), and (x2, y2). For each point, we 'toggle' its presence in our HashSet. To use a Point object in a HashSet, we need to properly implement equals() and hashCode(). A simpler way is to represent each point as a string, e.g., "x,y".
Verification: After the loop, we perform two final checks:
1. Area Check: Calculate the area of the bounding box: (maxX - minX) * (maxY - minY). This must be equal to the total area of the small rectangles we summed up. If not, it implies there's an overlap (summed area is too large) or a gap (summed area is too small).
2. Corner Check: The HashSet should contain exactly four points. These four points must be the corners of the bounding box we found: (minX, minY), (minX, maxY), (maxX, minY), and (maxX, maxY). If the set size is not 4, or if it contains any other points, it means some internal corners didn't cancel out, indicating an overlap or an imperfect tiling.

If both conditions are met, the rectangles form a perfect cover.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean isRectangleCover(int[][] rectangles) {6        if (rectangles == null || rectangles.length == 0) {7            return false;8        }9 10        int minX = Integer.MAX_VALUE;11        int minY = Integer.MAX_VALUE;12        int maxX = Integer.MIN_VALUE;13        int maxY = Integer.MIN_VALUE;14 15        long totalArea = 0;16        Set<String> cornerPoints = new HashSet<>();17 18        for (int[] rect : rectangles) {19            int x1 = rect[0];20            int y1 = rect[1];21            int x2 = rect[2];22            int y2 = rect[3];23 24            // Update bounding box coordinates25            minX = Math.min(minX, x1);26            minY = Math.min(minY, y1);27            maxX = Math.max(maxX, x2);28            maxY = Math.max(maxY, y2);29 30            // Calculate and sum the area31            totalArea += (long)(x2 - x1) * (long)(y2 - y1);32 33            // Four corner points of the current rectangle34            String p1 = x1 + "," + y1;35            String p2 = x1 + "," + y2;36            String p3 = x2 + "," + y1;37            String p4 = x2 + "," + y2;38 39            // Toggle the presence of each corner point in the set40            if (!cornerPoints.add(p1)) cornerPoints.remove(p1);41            if (!cornerPoints.add(p2)) cornerPoints.remove(p2);42            if (!cornerPoints.add(p3)) cornerPoints.remove(p3);43            if (!cornerPoints.add(p4)) cornerPoints.remove(p4);44        }45 46        // 1. Area Check47        long expectedArea = (long)(maxX - minX) * (long)(maxY - minY);48        if (totalArea != expectedArea) {49            return false;50        }51 52        // 2. Corner Check53        if (cornerPoints.size() != 4) {54            return false;55        }56 57        // Check if the remaining points are the corners of the bounding box58        if (!cornerPoints.contains(minX + "," + minY)) return false;59        if (!cornerPoints.contains(minX + "," + maxY)) return false;60        if (!cornerPoints.contains(maxX + "," + minY)) return false;61        if (!cornerPoints.contains(maxX + "," + maxY)) return false;62 63        return true;64    }65}

Complexity

Time

O(N), where N is the number of rectangles. We iterate through the list of rectangles once, and each operation inside the loop (math, set operations) takes constant time on average.

Space

O(N), as the `HashSet` of corner points can store up to 4N points in the worst case (if no corners are shared).

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Relatively simple to implement once the core geometric properties are understood.
Avoids complex geometric calculations or data structures like sweep-lines or segment trees.

Cons

The logic is based on a non-obvious insight, which might not be immediately apparent.
Can be susceptible to integer overflow if coordinates or areas are very large, requiring the use of long for area calculations.

Solutions

Solution

1class Solution {2public3  boolean isRectangleCover(int[][] rectangles) {4    long area = 0;5    int minX = rectangles[0][0], minY = rectangles[0][1];6    int maxX = rectangles[0][2], maxY = rectangles[0][3];7    Map<Pair, Integer> cnt = new HashMap<>();8    for (int[] r : rectangles) {9      area += (r[2] - r[0]) * (r[3] - r[1]);10      minX = Math.min(minX, r[0]);11      minY = Math.min(minY, r[1]);12      maxX = Math.max(maxX, r[2]);13      maxY = Math.max(maxY, r[3]);14      cnt.merge(new Pair(r[0], r[1]), 1, Integer : : sum);15      cnt.merge(new Pair(r[0], r[3]), 1, Integer : : sum);16      cnt.merge(new Pair(r[2], r[3]), 1, Integer : : sum);17      cnt.merge(new Pair(r[2], r[1]), 1, Integer : : sum);18    }19    if (area != (long)(maxX - minX) * (maxY - minY) ||20        cnt.getOrDefault(new Pair(minX, minY), 0) != 1 ||21        cnt.getOrDefault(new Pair(minX, maxY), 0) != 1 ||22        cnt.getOrDefault(new Pair(maxX, maxY), 0) != 1 ||23        cnt.getOrDefault(new Pair(maxX, minY), 0) != 1) {24      return false;25    }26    cnt.remove(new Pair(minX, minY));27    cnt.remove(new Pair(minX, maxY));28    cnt.remove(new Pair(maxX, maxY));29    cnt.remove(new Pair(maxX, minY));30    return cnt.values().stream().allMatch(c->c == 2 || c == 4);31  }32private33  static class Pair {34    final int first;35    final int second;36    Pair(int first, int second) {37      this.first = first;38      this.second = second;39    }40    @Override public boolean equals(Object o) {41      if (this == o) {42        return true;43      }44      if (o == null || getClass() != o.getClass()) {45        return false;46      }47      Pair pair = (Pair)o;48      return first == pair.first && second == pair.second;49    }50    @Override public int hashCode() {51      return Objects.hash(first, second);52    }53  }54}

1#include <bits/stdc++.h> using namespace std ; class Solution { public: bool isRectangleCover ( vector < vector < int >>& rectangles ) { long long area = 0 ; int minX = rectangles [ 0 ][ 0 ], minY = rectangles [ 0 ][ 1 ]; int maxX = rectangles [ 0 ][ 2 ], maxY = rectangles [ 0 ][ 3 ]; using pii = pair < int , int > ; map < pii , int > cnt ; for ( auto & r : rectangles ) { area += ( r [ 2 ] - r [ 0 ]) * ( r [ 3 ] - r [ 1 ]); minX = min ( minX , r [ 0 ]); minY = min ( minY , r [ 1 ]); maxX = max ( maxX , r [ 2 ]); maxY = max ( maxY , r [ 3 ]); ++ cnt [{ r [ 0 ], r [ 1 ]}]; ++ cnt [{ r [ 0 ], r [ 3 ]}]; ++ cnt [{ r [ 2 ], r [ 3 ]}]; ++ cnt [{ r [ 2 ], r [ 1 ]}]; } if ( area != ( long long ) ( maxX - minX ) * ( maxY - minY ) || cnt [{ minX , minY }] != 1 || cnt [{ minX , maxY }] != 1 || cnt [{ maxX , maxY }] != 1 || cnt [{ maxX , minY }] != 1 ) { return false ; } cnt . erase ({ minX , minY }); cnt . erase ({ minX , maxY }); cnt . erase ({ maxX , maxY }); cnt . erase ({ maxX , minY }); return all_of ( cnt . begin (), cnt . end (), []( pair < pii , int > e ) { return e . second == 2 || e . second == 4 ; }); } };

1class Solution:2    def isRectangleCover(self, rectangles: List[List[int]]) -> bool: area = 0 minX, minY = rectangles[0][0], rectangles[0][1] maxX, maxY = rectangles[0][2], rectangles[0][3] cnt = defaultdict(int) for r in rectangles: area += (r[2] - r[0]) * (r[3] - r[1]) minX = min(minX, r[0]) minY = min(minY, r[1]) maxX = max(maxX, r[2]) maxY = max(maxY, r[3]) cnt[(r[0], r[1])] += 1 cnt[(r[0], r[3])] += 1 cnt[(r[2], r[3])] += 1 cnt[(r[2], r[1])] += 1 if (area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, maxY)] != 1 or cnt[(maxX, minY)] != 1): return False del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, maxY)], cnt[(maxX, minY)] return all(c == 2 or c == 4 for c in cnt . values())

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.

← Previous

Previous problem

Next problem