How do you solve Perfect Rectangle on LeetCode?

Perfect Rectangle (LeetCode #391) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Each rectangle contributes exactly four corners, and corners can either be unique or shared.

What is the brute force solution for Perfect Rectangle?

The brute force approach for Perfect Rectangle is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every pair of rectangles to see if they overlap or if there are gaps between them. This is simple but inefficient, as it doesn't leverage any geometric properties of the rectangles. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Perfect Rectangle?

Perfect Rectangle uses the following concepts: Array, Hash Table, Math, Geometry, Sweep Line. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Perfect Rectangle?

Always visualize the problem with a diagram; it helps in understanding overlaps and gaps. Discuss your thought process clearly; explain how you would handle edge cases. Practice coding the solution on a whiteboard or in a shared document to simulate the interview environment.

What are common mistakes when solving Perfect Rectangle?

Failing to check for overlaps correctly, leading to false positives. Not accounting for the exact number of unique corners required.

#391

Perfect Rectangle

Hard

ArrayHash TableMathGeometrySweep LineHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a combination of a corner counting strategy and a bounding box check. This approach efficiently determines if the rectangles form a perfect rectangle by ensuring all corners are accounted for correctly and that there are no overlaps.

⚙️

Algorithm

4 steps

1Step 1: Initialize a dictionary to count occurrences of corners.
2Step 2: For each rectangle, update the corner counts.
3Step 3: Identify the bounding rectangle by finding the minimum and maximum x and y coordinates.
4Step 4: Check if the corner counts match the expected corners of the bounding rectangle and if all other corners have even counts.

solution.py20 lines

1# Full working Python code
2from collections import defaultdict
3
4def isRectangleCover(rectangles):
5    corners = defaultdict(int)
6    min_x = min_y = float('inf')
7    max_x = max_y = float('-inf')
8    for x1, y1, x2, y2 in rectangles:
9        corners[(x1, y1)] += 1
10        corners[(x1, y2)] += 1
11        corners[(x2, y1)] += 1
12        corners[(x2, y2)] += 1
13        min_x = min(min_x, x1)
14        min_y = min(min_y, y1)
15        max_x = max(max_x, x2)
16        max_y = max(max_y, y2)
17    expected_corners = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
18    if len(corners) != 4 or any(corners[corner] % 2 != 0 for corner in corners if corner not in expected_corners):
19        return False
20    return True

ℹ

Complexity note: The complexity is O(n) because we only traverse the list of rectangles once to count corners and determine the bounding box.

1Each rectangle contributes exactly four corners, and corners can either be unique or shared.
2The bounding rectangle must encompass all rectangles without any gaps or overlaps.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.