Perfect Rectangle solution and explanation
Google
9 more videos on this problem
391. Perfect Rectangle (Leetcode Hard)Programming Live with Larry · 14:33 · 4K views
花花酱 LeetCode 391. Perfect Rectangle - 刷题找工作 EP255Hua Hua · 10:16 · 3K views
LeetCode 391 | Perfect Rectangle | HashSet | Debug | JavaSleepy Cracker · 13:47 · 1K views
How to Find a Perfect Rectangle || #arshgoyal #6companies30days #revisewitharshpradeep konda · 13:45 · 868 views
Leetcode 0391. Perfect RectangleFearless Learner · 16:57 · 530 views
(Leetcode) Perfect RectangleRoel Van de Paar · 3:05 · 326 views
[LeetCode][Hard]391 Perfect Rectanglena982 · 11:50 · 215 views
LeetCode 391: Perfect RectangleAlitaCode · 30:48 · 126 views
LeetCode Weekly Contest 2 389 , 390 , 391 Find the Difference, Elimination Game, Perfect RectangleOm · 16:41 · 116 views
No Sound Leetcode 391: Perfect RectangleExtremeProgrammer · 2:30 · 113 views
The problem
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 <= 105
Approach overview
Problem 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 1: Approach 1 - Use a Sweep Line Algorithm
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:
- For a beginning of a rectangle, add its y-interval to the active set.
- For an end of a rectangle, remove its y-interval from the active set.
- By tracking the active y-intervals, we can ensure they are disjoint and cover the y-range properly after processing two events with the same x-coordinate.
from sortedcontainers import SortedDict
def isRectangleCover(rectangles):
events = []
for x1, y1, x2, y2 in rectangles:
events.append((x1, y1, y2, 1))
events.append((x2, y1, y2, -1))
events.sort()
active = SortedDict()
area = 0
for x, y1, y2, typ in events:
if active:
y_active = sorted(active.items())
current_y = 0
for y_start, y_end in y_active:
current_y = max(current_y, y_start)
area += y_end - current_y
current_y = max(current_y, y_end)
if typ == 1: # Adding interval
if (y1, y2) in active:
active[(y1, y2)] += 1
else:
active[(y1, y2)] = 1
else: # Removing interval
if (y1, y2) in active:
active[(y1, y2)] -= 1
if active[(y1, y2)] == 0:
del active[(y1, y2)]
bottom_left = (min(x for x, _, _, _ in events), min(y1 for _, y1, _, _ in events))
top_right = (max(x for x, _, _, _ in events), max(y2 for _, _, y2, _ in events))
total_area = (top_right[0] - bottom_left[0]) * (top_right[1] - bottom_left[1])
return area == total_areafunction isRectangleCover(rectangles) {
const events = [];
for (let [x1, y1, x2, y2] of rectangles) {
events.push([x1, y1, y2, 1]);
events.push([x2, y1, y2, -1]);
}
events.sort((a, b) => a[0] - b[0]);
const active = new Map();
let area = 0;
let lastX = [...new Set(events.map(event => event[0]))];
for (let x of lastX) {
let new_events = events.filter(e => e[0] === x);
if (active.size) {
let y_intervals = Array.from(active.entries()).sort((a, b) => a[0] - b[0]);
let current_y = 0;
for (let [y1, y2_interval] of y_intervals) {
if (current_y < y1) return false;
current_y = Math.max(current_y, y2_interval[0]);
}
}
for (let [x, y1, y2, typ] of new_events) {
if (typ === 1) { // adding
if (active.has(y1)) {
let y2_vals = active.get(y1);
active.set(y1, [Math.max(...y2_vals, y2)]);
} else {
active.set(y1, [y2]);
}
} else { // removing
if (active.has(y1)) {
let y2_vals = active.get(y1).filter(el => el !== y2);
if (y2_vals.length === 0) active.delete(y1);
else active.set(y1, y2_vals);
}
}
}
}
const bottom_left_x = Math.min(...rectangles.map(r => r[0]));
const bottom_left_y = Math.min(...rectangles.map(r => r[1]));
const top_right_x = Math.max(...rectangles.map(r => r[2]));
const top_right_y = Math.max(...rectangles.map(r => r[3]));
const expected_area = (top_right_x - bottom_left_x) * (top_right_y - bottom_left_y);
return area === expected_area;
}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.
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.
Approach 2: Approach 2 - Use of Set for Corner Tracking
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.
import java.util.HashSet;
import java.util.Set;
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int area = 0;
int xMin = Integer.MAX_VALUE;
int yMin = Integer.MAX_VALUE;
int xMax = Integer.MIN_VALUE;
int yMax = Integer.MIN_VALUE;
Set<String> set = new HashSet<>();
for (int[] rect : rectangles) {
int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
xMin = Math.min(xMin, x1);
yMin = Math.min(yMin, y1);
xMax = Math.max(xMax, x2);
yMax = Math.max(yMax, y2);
area += (x2 - x1) * (y2 - y1);
String[] corners = { x1 + "," + y1, x1 + "," + y2, x2 + "," + y1, x2 + "," + y2 };
for (String corner : corners) {
if (!set.add(corner)) set.remove(corner);
}
}
if (!set.contains(xMin + "," + yMin) || !set.contains(xMin + "," + yMax) ||
!set.contains(xMax + "," + yMin) || !set.contains(xMax + "," + yMax) || set.size() != 4) {
return false;
}
int expectedArea = (xMax - xMin) * (yMax - yMin);
return expectedArea == area;
}
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsRectangleCover(int[][] rectangles) {
int xMin = int.MaxValue, yMin = int.MaxValue;
int xMax = int.MinValue, yMax = int.MinValue;
HashSet<string> set = new HashSet<string>();
int area = 0;
foreach (var rect in rectangles) {
int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
xMin = Math.Min(xMin, x1);
yMin = Math.Min(yMin, y1);
xMax = Math.Max(xMax, x2);
yMax = Math.Max(yMax, y2);
area += (x2 - x1) * (y2 - y1);
string[] corners = new string[] {
x1 + "," + y1,
x1 + "," + y2,
x2 + "," + y1,
x2 + "," + y2
};
foreach (var corner in corners) {
if (!set.Add(corner)) set.Remove(corner);
}
}
if (!set.Contains(xMin + "," + yMin) || !set.Contains(xMin + "," + yMax) ||
!set.Contains(xMax + "," + yMin) || !set.Contains(xMax + "," + yMax) || set.Count != 4) {
return false;
}
int expectedArea = (xMax - xMin) * (yMax - yMin);
return area == expectedArea;
}
}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 3: Default Approach
#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;
});
}
};type pair struct {
first int
second int
}
func isRectangleCover(rectangles [][]int) bool {
area := 0
minX, minY := rectangles[0][0], rectangles[0][1]
maxX, maxY := rectangles[0][2], rectangles[0][3]
cnt := make(map[pair]int)
for _, r := range 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[pair{r[0], r[1]}]++
cnt[pair{r[0], r[3]}]++
cnt[pair{r[2], r[3]}]++
cnt[pair{r[2], r[1]}]++
}
if area != (maxX-minX)*(maxY-minY) ||
cnt[pair{minX, minY}] != 1 ||
cnt[pair{minX, maxY}] != 1 ||
cnt[pair{maxX, maxY}] != 1 ||
cnt[pair{maxX, minY}] != 1 {
return false
}
delete(cnt, pair{minX, minY})
delete(cnt, pair{minX, maxY})
delete(cnt, pair{maxX, maxY})
delete(cnt, pair{maxX, minY})
for _, c := range cnt {
if c != 2 && c != 4 {
return false
}
}
return true
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Perfect Rectangle easy or hard?
Perfect Rectangle is classified as a Hard problem. The difficulty comes from identifying the corner parity property and ensuring both area equality and corner uniqueness conditions hold simultaneously.
Perfect Rectangle Python/Java solution
Python solutions often implement the corner tracking method using a set of tuples and simple area accumulation. Java implementations typically use a HashSet of string or pair representations for corners. Both versions achieve O(n) time and O(n) space complexity.
How to solve Perfect Rectangle in O(n)?
Compute the bounding rectangle using the minimum and maximum coordinates across all rectangles. Track each rectangle's four corners in a hash set, adding or removing them as they appear. After processing all rectangles, verify that the set contains exactly the four bounding corners and that the total small-rectangle area equals the bounding rectangle area.
What is the best approach for Perfect Rectangle?
The corner set tracking method is typically the best approach. It tracks rectangle corners in a hash set and verifies that only four outer corners remain while the total area matches the bounding rectangle. This solution runs in O(n) time and O(n) space and is concise enough for interviews.
Is Perfect Rectangle asked at Google/Amazon/Meta?
Perfect Rectangle appears in interviews at companies that test computational geometry or advanced hashing patterns, including Google and Amazon in some interview reports. It is considered a challenging problem because it combines geometry reasoning with hash-based invariants.
What data structure is used in Perfect Rectangle?
The most common solution uses a hash set to track rectangle corners and ensure internal corners cancel out. The sweep line approach uses sorted events and a balanced structure or ordered set to maintain active intervals during the scan.
What is the time complexity of Perfect Rectangle?
The optimal corner tracking solution runs in O(n) time because each rectangle contributes four constant-time set operations. Space complexity is O(n) for storing unique corners. The sweep line approach takes O(n log n) time due to sorting edge events.