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.

Description Solution Video 14:33

391. Perfect Rectangle

Hard39.4% acceptance3 companies

Given an array rectangles where rectangles[i] = [x_i, y_i, a_i, b_i] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (x_i, y_i) and the top-right point of it is (a_i, b_i).

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 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i < a_i <= 10⁵
-10⁵ <= y_i < b_i <= 10⁵

Asked at 3 companies

Google Amazon Meta

Topics

Array Line Sweep

14:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]

Input

[[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]

Input

[[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]

Your code is saved on this device.Solution