Perfect Rectangle — Solution in Python, Java & C++
Perfect Rectangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and hash table.
Perfect Rectangle is a hard coding problem on arrays, hash table and math, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Math, Geometry
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Each rectangles[i] = [xi, yi, ai, bi] is an axis-aligned rectangle with bottom-left corner (xi, yi) and top-right corner (ai, bi); every rectangle has positive width and height.
Return true if the rectangles together form one exact rectangle: their union is a rectangle, and no two of them overlap (sharing edges is fine, sharing any area is not). Gaps and overlaps both make the answer false.
Example 1
Input: rectangles = [[0,0,2,1],[2,0,3,2],[1,2,3,3],[0,1,1,3],[1,1,2,2]]
Output: true
Explanation: A 'pinwheel' of five pieces tiling the 3 x 3 square.
Example 2
Input: rectangles = [[0,0,2,2],[2,0,3,1]]
Output: false
Explanation: The square from (2,1) to (3,2) is missing.
Example 3
Input: rectangles = [[0,0,2,2],[1,1,3,3],[0,2,1,3],[2,0,3,1]]
Output: false
Explanation: The first two overlap on the square from (1,1) to (2,2).
Constraints
1 <= rectangles.length <= 2 * 10^4rectangles[i].length == 4-10^5 <= xi < ai <= 10^5-10^5 <= yi < bi <= 10^5
Hints for Perfect Rectangle
Hint 1
The target must be the bounding box of all the rectangles — and the total area must equal its area.
Hint 2
Equal area still allows an overlap that cancels a gap. Look at the corners: inside a perfect tiling, every corner point is shared by an even number of rectangles.
Hint 3
Toggle every rectangle's four corners in a set. A perfect cover leaves exactly the four corners of the bounding box.
How to solve Perfect Rectangle
Two conditions together characterise a perfect cover: the areas add up to the bounding box's area, and every corner point occurs an even number of times except the four corners of the bounding box, which occur once.
Approach
- Track the bounding box
minX, minY, maxX, maxYand the total area (in 64 bits). - For each rectangle, toggle its four corner points in a set: add a point that is absent, remove one that is present.
- Return
falseif the total area differs from(maxX - minX) · (maxY - minY). - Return
trueexactly when the set holds four points and they are the bounding box's corners.
Why it works
In a perfect tiling, any point that is a corner of some piece but not of the big rectangle is surrounded by pieces meeting there in pairs — two (on an edge) or four (inside) — so it toggles out; the four outer corners belong to exactly one piece each and stay. Conversely, if the areas match but some region is covered twice, a matching region must be uncovered; the boundary of the doubled or missing region creates a corner point shared by an odd number of pieces somewhere other than the outer corners, which the set catches. Area alone misses overlap-plus-gap, and corners alone miss some overlaps; together they are exact.
Complexity
- Time —
O(n) expected with a hash set - Space —
O(n)
Pitfalls
- Areas reach (2·10^5)² = 4·10^10 per rectangle — sum them in 64 bits.
- Use toggling (parity), not counting into a set once; a corner shared by two pieces must vanish.
- The bounding box is computed from the minimum of left/bottom edges and the maximum of right/top edges, not from any single rectangle.
Reference solution
Python
from typing import List
def isRectangleCover(rectangles: List[List[int]]) -> bool:
min_x = min(r[0] for r in rectangles)
min_y = min(r[1] for r in rectangles)
max_x = max(r[2] for r in rectangles)
max_y = max(r[3] for r in rectangles)
area = 0
corners = set()
for x1, y1, x2, y2 in rectangles:
area += (x2 - x1) * (y2 - y1)
for p in ((x1, y1), (x1, y2), (x2, y1), (x2, y2)):
if p in corners:
corners.remove(p)
else:
corners.add(p)
if area != (max_x - min_x) * (max_y - min_y):
return False
return corners == {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}Java
public static boolean isRectangleCover(int[][] rectangles) {
long minX = Long.MAX_VALUE, minY = Long.MAX_VALUE, maxX = Long.MIN_VALUE, maxY = Long.MIN_VALUE;
long area = 0;
Set<Long> corners = new HashSet<>();
for (int[] r : rectangles) {
minX = Math.min(minX, r[0]); minY = Math.min(minY, r[1]);
maxX = Math.max(maxX, r[2]); maxY = Math.max(maxY, r[3]);
area += (long) (r[2] - r[0]) * (r[3] - r[1]);
long[] keys = { coverKey(r[0], r[1]), coverKey(r[0], r[3]), coverKey(r[2], r[1]), coverKey(r[2], r[3]) };
for (long key : keys) {
if (!corners.remove(key)) corners.add(key);
}
}
if (area != (maxX - minX) * (maxY - minY)) return false;
if (corners.size() != 4) return false;
return corners.contains(coverKey(minX, minY)) && corners.contains(coverKey(minX, maxY))
&& corners.contains(coverKey(maxX, minY)) && corners.contains(coverKey(maxX, maxY));
}
private static long coverKey(long x, long y) {
return (x + 100000L) * 200001L + (y + 100000L);
}C++
bool isRectangleCover(vector<vector<int>>& rectangles) {
long long minX = LLONG_MAX, minY = LLONG_MAX, maxX = LLONG_MIN, maxY = LLONG_MIN;
long long area = 0;
set<pair<long long, long long>> corners;
for (auto& r : rectangles) {
minX = min(minX, (long long) r[0]); minY = min(minY, (long long) r[1]);
maxX = max(maxX, (long long) r[2]); maxY = max(maxY, (long long) r[3]);
area += (long long) (r[2] - r[0]) * (r[3] - r[1]);
pair<long long, long long> ps[4] = { {r[0], r[1]}, {r[0], r[3]}, {r[2], r[1]}, {r[2], r[3]} };
for (auto& p : ps) {
if (corners.count(p)) corners.erase(p); else corners.insert(p);
}
}
if (area != (maxX - minX) * (maxY - minY)) return false;
if (corners.size() != 4) return false;
return corners.count({minX, minY}) && corners.count({minX, maxY})
&& corners.count({maxX, minY}) && corners.count({maxX, maxY});
}JavaScript
var isRectangleCover = function(rectangles) {
var minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
var area = 0;
var corners = new Set();
var toggle = function(x, y) {
var key = x + "," + y;
if (corners.has(key)) corners.delete(key); else corners.add(key);
};
for (var i = 0; i < rectangles.length; i++) {
var r = rectangles[i];
minX = Math.min(minX, r[0]); minY = Math.min(minY, r[1]);
maxX = Math.max(maxX, r[2]); maxY = Math.max(maxY, r[3]);
area += (r[2] - r[0]) * (r[3] - r[1]);
toggle(r[0], r[1]); toggle(r[0], r[3]); toggle(r[2], r[1]); toggle(r[2], r[3]);
}
if (area !== (maxX - minX) * (maxY - minY)) return false;
if (corners.size !== 4) return false;
return corners.has(minX + "," + minY) && corners.has(minX + "," + maxY) &&
corners.has(maxX + "," + minY) && corners.has(maxX + "," + maxY);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets