Table of Contents
Perfect Rectangle – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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 * 104rectangles[i].length == 4-105 <= xi, yi, ai, bi <= 105
C++ Perfect Rectangle LeetCode Solution
class Solution {
private:
struct comp {
bool operator () (const pair<int, int>& a, const pair<int, int>& b) { return a.second <= b.first; }
};
public:
bool isRectangleCover(vector<vector<int>>& rectangles) {
int area = 0, xmin = INT_MAX, ymin = INT_MAX, xmax = INT_MIN, ymax = INT_MIN;
vector<vector<int>> verticalEdges; // x, insertion/deletion event, ysmall, ylarge
multiset<pair<int, int>, comp> s; // for detecting overlaps
// Calculate area, and configure verticalEdges
for (auto v : rectangles) {
area += (v[2] - v[0]) * (v[3] - v[1]);
xmin = min(xmin, v[0]), ymin = min(ymin, v[1]), xmax = max(xmax, v[2]), ymax = max(ymax, v[3]);
verticalEdges.push_back({v[0], 1, v[1], v[3]}), verticalEdges.push_back({v[2], -1, v[1], v[3]});
}
if (area != (xmax - xmin) * (ymax - ymin)) { return false; }
// Check if any overlap exists
sort(verticalEdges.begin(), verticalEdges.end());
for (auto v : verticalEdges) {
auto it = s.find(make_pair(v[2], v[3]));
if (v[1] > 0) { // left edge, insertion event
if (it != s.end()) { return false; } // found an overlap
s.insert(make_pair(v[2], v[3]));
} else { // right edge, deletion event
s.erase(it);
}
}
return true;
}
};
Java Perfect Rectangle LeetCode Solution
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles.length == 0 || rectangles[0].length == 0) return false;
int x1 = Integer.MAX_VALUE;
int x2 = Integer.MIN_VALUE;
int y1 = Integer.MAX_VALUE;
int y2 = Integer.MIN_VALUE;
HashSet<String> set = new HashSet<String>();
int area = 0;
for (int[] rect : rectangles) {
x1 = Math.min(rect[0], x1);
y1 = Math.min(rect[1], y1);
x2 = Math.max(rect[2], x2);
y2 = Math.max(rect[3], y2);
area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
String s1 = rect[0] + " " + rect[1];
String s2 = rect[0] + " " + rect[3];
String s3 = rect[2] + " " + rect[3];
String s4 = rect[2] + " " + rect[1];
if (!set.add(s1)) set.remove(s1);
if (!set.add(s2)) set.remove(s2);
if (!set.add(s3)) set.remove(s3);
if (!set.add(s4)) set.remove(s4);
}
if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) return false;
return area == (x2-x1) * (y2-y1);
}
Python 3 Perfect Rectangle LeetCode Solution
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
area = 0
corners = set()
a = lambda: (Y-y) * (X-x)
for x, y, X, Y in rectangles:
area += a()
corners ^= {(x,y), (x,Y), (X,y), (X,Y)}
if len(corners) != 4: return False
x, y = min(corners, key=lambda x: x[0] + x[1])
X, Y = max(corners, key=lambda x: x[0] + x[1])
return a() == area
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
