Perfect Rectangle — LeetCode 391 Python Solution
HardGeometryArrayHash TableMathLine Sweep
- Problem
- #391
- Pattern
- Math and Number Theory
- Reading time
- 6 min
- Source
- leetcode.com
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).
Example
- 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.
Python solution
Python
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
area = 0
minX, minY = rectangles[0][0], rectangles[0][1]
maxX, maxY = rectangles[0][2], rectangles[0][3]
cnt = defaultdict(int)
for r in 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])] += 1
cnt[(r[0], r[3])] += 1
cnt[(r[2], r[3])] += 1
cnt[(r[2], r[1])] += 1
if (
area != (maxX - minX) * (maxY - minY)
or cnt[(minX, minY)] != 1
or cnt[(minX, maxY)] != 1
or cnt[(maxX, maxY)] != 1
or cnt[(maxX, minY)] != 1
):
return False
del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, maxY)], cnt[(maxX, minY)]
return all(c == 2 or c == 4 for c in cnt.values())Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 391. Perfect Rectangle is filed here because LeetCode tags it Math and Geometry, which is the vocabulary this hub collects.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 391. Perfect Rectangle?
- LeetCode 391. Perfect Rectangle is rated Hard on LeetCode.
- What is the time complexity of LeetCode 391. Perfect Rectangle?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 391. Perfect Rectangle?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 391. Perfect Rectangle cover?
- LeetCode 391. Perfect Rectangle is tagged Geometry, Array, Hash Table, Math and Line Sweep on LeetCode.