In this guide, you will get 391. Perfect Rectangle LeetCode Solution with the best time and space complexity. The solution to Perfect Rectangle problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
391. Perfect Rectangle LeetCode Solution in C++
class Solution {
public:
bool isRectangleCover(vector<vector<int>>& rectangles) {
int area = 0;
int x1 = INT_MAX;
int y1 = INT_MAX;
int x2 = INT_MIN;
int y2 = INT_MIN;
unordered_set<string> corners;
for (const vector<int>& r : rectangles) {
area += (r[2] - r[0]) * (r[3] - r[1]);
x1 = min(x1, r[0]);
y1 = min(y1, r[1]);
x2 = max(x2, r[2]);
y2 = max(y2, r[3]);
// the four points of the current rectangle
const vector<string> points{to_string(r[0]) + " " + to_string(r[1]),
to_string(r[0]) + " " + to_string(r[3]),
to_string(r[2]) + " " + to_string(r[1]),
to_string(r[2]) + " " + to_string(r[3])};
for (const string& point : points)
if (!corners.insert(point).second)
corners.erase(point);
}
if (corners.size() != 4)
return false;
if (!corners.contains(to_string(x1) + " " + to_string(y1)) ||
!corners.contains(to_string(x1) + " " + to_string(y2)) ||
!corners.contains(to_string(x2) + " " + to_string(y1)) ||
!corners.contains(to_string(x2) + " " + to_string(y2)))
return false;
return area == (x2 - x1) * (y2 - y1);
}
}; /* code provided by PROGIEZ */
391. Perfect Rectangle LeetCode Solution in Java
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
int area = 0;
int x1 = Integer.MAX_VALUE;
int y1 = Integer.MAX_VALUE;
int x2 = Integer.MIN_VALUE;
int y2 = Integer.MIN_VALUE;
Set<String> corners = new HashSet<>();
for (int[] r : rectangles) {
area += (r[2] - r[0]) * (r[3] - r[1]);
x1 = Math.min(x1, r[0]);
y1 = Math.min(y1, r[1]);
x2 = Math.max(x2, r[2]);
y2 = Math.max(y2, r[3]);
// the four points of the current rectangle
String[] points = new String[] {r[0] + " " + r[1], //
r[0] + " " + r[3], //
r[2] + " " + r[1], //
r[2] + " " + r[3]};
for (final String point : points)
if (!corners.add(point))
corners.remove(point);
}
if (corners.size() != 4)
return false;
if (!corners.contains(x1 + " " + y1) || //
!corners.contains(x1 + " " + y2) || //
!corners.contains(x2 + " " + y1) || //
!corners.contains(x2 + " " + y2))
return false;
return area == (x2 - x1) * (y2 - y1);
}
} // code provided by PROGIEZ
391. Perfect Rectangle LeetCode Solution in Python
class Solution:
def isRectangleCover(self, rectangles: list[list[int]]) -> bool:
area = 0
x1 = math.inf
y1 = math.inf
x2 = -math.inf
y2 = -math.inf
corners: set[tuple[int, int]] = set()
for x, y, a, b in rectangles:
area += (a - x) * (b - y)
x1 = min(x1, x)
y1 = min(y1, y)
x2 = max(x2, a)
y2 = max(y2, b)
# the four points of the current rectangle
for point in [(x, y), (x, b), (a, y), (a, b)]:
if point in corners:
corners.remove(point)
else:
corners.add(point)
if len(corners) != 4:
return False
if ((x1, y1) not in corners or
(x1, y2) not in corners or
(x2, y1) not in corners or
(x2, y2) not in corners):
return False
return area == (x2 - x1) * (y2 - y1) # code by PROGIEZ
