Skip to main content
Talentd

Perfect Rectangle - Solution & Explanation

HardArrayLine Sweep12 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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 * 104
  • rectangles[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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaC#

Java

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1 - Use a Sweep Line Algorithm

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 - Use of Set for Corner Tracking

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sweep Line AlgorithmO(n log n)O(n)When solving general rectangle overlap or geometry problems requiring ordered edge processing
Corner Set TrackingO(n)O(n)Best choice for interviews and competitive programming due to simple logic and linear time

Video Solution

391. Perfect Rectangle (Leetcode Hard) • Programming Live with Larry • 4,121 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Perfect Rectangle with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays