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] = [x`

represents an axis-aligned rectangle. The bottom-left point of the rectangle is _{i}, y_{i}, a_{i}, b_{i}]`(x`

and the top-right point of it is _{i}, y_{i})`(a`

._{i}, b_{i})

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:trueExplanation: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:falseExplanation: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:falseExplanation:Because two of the rectangles overlap with each other.

**Constraints:**

`1 <= rectangles.length <= 2 * 10`

^{4}`rectangles[i].length == 4`

`-10`

^{5}<= x_{i}, y_{i}, a_{i}, b_{i}<= 10^{5}

# 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