# Perfect Rectangle
**Difficulty:** HARD
[External](https://leetcode.com/problems/perfect-rectangle)
Canonical: https://scaleengineer.com/dsa/problems/perfect-rectangle
**Patterns:** [Line Sweep](https://scaleengineer.com/dsa/patterns/line-sweep)
**Data structures:** Array
---
## Problem
\[Fetch error\]

# Approaches
## Sweep-Line Algorithm
This approach treats the vertical edges of the rectangles as events along the x-axis. We sweep a vertical line from left to right, maintaining the set of active rectangles (and their y-intervals) that the sweep line is currently intersecting. At each step, we check if the active y-intervals form a single, contiguous block that matches the height of the overall bounding rectangle.
**Time:** O(N log N), where N is the number of rectangles. The dominant operation is sorting the 2N events. Processing each event can be done in O(log N) or O(1) depending on the data structure used for the sweep line. · **Space:** O(N) to store the 2N events and the data structure for the active y-intervals.
**Pros:** A standard and powerful technique for a wide range of computational geometry problems.; Can be adapted to solve similar problems involving intervals or shapes.
**Cons:** Significantly more complex to implement correctly compared to the point-counting method.; The logic for managing the active intervals and checking for perfect coverage at each step is non-trivial and error-prone.; Can be less efficient due to the sorting step and the complexity of operations on the interval data structure.
### Explanation
The core idea is to process the rectangles' boundaries in sorted order of their x-coordinates.

*   **Event Creation**: For each rectangle `[x1, y1, x2, y2]`, we generate two events: a 'start' event at `x1` for the interval `[y1, y2]`, and an 'end' event at `x2` for the same interval. These events are stored in a list.

*   **Sorting**: The list of events is sorted primarily by the x-coordinate. This creates a timeline of when rectangles begin and end as we move from left to right.

*   **Sweep and Verify**: We iterate through the sorted events. We maintain a data structure (like a sorted list or a balanced tree) of the active y-intervals currently intersected by our sweep line. 
    *   Between any two consecutive x-coordinates from our event list, the set of active y-intervals must be stable. We check if these intervals are perfectly stitched together (no gaps, no overlaps) and if their total length equals the height of the final bounding box (`maxY - minY`).
    *   When the sweep line hits an x-coordinate with events:
        *   For 'start' events, we add their y-intervals to our active set.
        *   For 'end' events, we remove their y-intervals.

*   **Bounding Box**: Before starting the sweep, we first iterate through all rectangles to find the overall bounding box (`minX`, `minY`, `maxX`, `maxY`). This is needed to know the target height (`maxY - minY`) for our sweep-line checks.

If at any point the check for a perfect vertical segment fails, we can immediately return `false`. If the sweep completes successfully, it means the rectangles form a perfect cover.

```java
// Note: A full implementation of a sweep-line algorithm is complex.
// The following is a conceptual outline demonstrating the logic.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;

        // Create events [x, type, y1, y2] where type=1 for start, -1 for end
        List<int[]> events = new ArrayList<>();
        for (int[] r : rectangles) {
            minX = Math.min(minX, r[0]);
            maxX = Math.max(maxX, r[2]);
            events.add(new int[]{r[0], 1, r[1], r[3]});
            events.add(new int[]{r[2], -1, r[1], r[3]});
        }
        Collections.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        // TreeMap to store the count of active intervals at each y-coordinate
        TreeMap<Integer, Integer> yCounts = new TreeMap<>();
        int i = 0;
        while (i < events.size()) {
            int currentX = events.get(i)[0];
            
            // For any x between the bounding box edges, check the active line
            if (currentX > minX && currentX < maxX) {
                if (yCounts.size() < 2) return false; // Must have at least a bottom and top
                int active = 0;
                int count = 0;
                for (int val : yCounts.values()) {
                    active += val;
                    if (active == 1) count++; // Segment where one rectangle is active
                    else if (active != 0) return false; // Overlap or other issue
                }
                if (count != 1) return false; // Must be one contiguous block
            }

            // Process all events at the current x-coordinate
            int j = i;
            while (j < events.size() && events.get(j)[0] == currentX) {
                int[] event = events.get(j);
                int type = event[1];
                int y1 = event[2];
                int y2 = event[3];
                yCounts.put(y1, yCounts.getOrDefault(y1, 0) + type);
                if (yCounts.get(y1) == 0) yCounts.remove(y1);
                yCounts.put(y2, yCounts.getOrDefault(y2, 0) - type);
                if (yCounts.get(y2) == 0) yCounts.remove(y2);
                j++;
            }
            i = j;
        }

        return true;
    }
}
```
### Algorithm
*   Create a list of events. For each rectangle `[x1, y1, x2, y2]`, add two events: a 'start' event `(x1, y1, y2)` and an 'end' event `(x2, y1, y2)`.
*   Sort the events based on their x-coordinate.
*   Determine the overall bounding box `(minX, minY, maxX, maxY)` by iterating through all rectangles once.
*   Initialize a sweep line and a data structure to track active y-intervals.
*   Iterate through the sorted events. At each x-coordinate, update the active y-intervals.
*   Between two consecutive event x-coordinates, verify that the active y-intervals form a single, non-overlapping segment that spans from `minY` to `maxY`.
*   If this condition holds for the entire sweep from `minX` to `maxX`, the rectangles form a perfect cover.

## Corner Point Counting and Area Summation
This highly efficient approach is based on a simple geometric insight. For a set of non-overlapping rectangles to form a single larger rectangle, two conditions must be met:
1.  The sum of the areas of the small rectangles must equal the area of the bounding box that encloses them.
2.  Except for the four corners of the bounding box, all other corners of the small rectangles must appear an even number of times (i.e., they must be shared by an even number of rectangles to 'cancel out').
**Time:** O(N), where N is the number of rectangles. We iterate through the list of rectangles once, and each operation inside the loop (math, set operations) takes constant time on average. · **Space:** O(N), as the `HashSet` of corner points can store up to 4N points in the worst case (if no corners are shared).
**Pros:** Extremely efficient with a linear time complexity.; Relatively simple to implement once the core geometric properties are understood.; Avoids complex geometric calculations or data structures like sweep-lines or segment trees.
**Cons:** The logic is based on a non-obvious insight, which might not be immediately apparent.; Can be susceptible to integer overflow if coordinates or areas are very large, requiring the use of `long` for area calculations.
### Explanation
The algorithm leverages these two properties for a very efficient check.

*   **Initialization**: We need variables to track the total area of all small rectangles and the coordinates of the overall bounding box (`minX`, `minY`, `maxX`, `maxY`). We also need a data structure to count the occurrences of each corner point. A `HashSet` is perfect for this: adding a point that already exists will be a no-op, so we can implement a toggle: if a point is in the set, we remove it; otherwise, we add it. At the end, the set will only contain points that appeared an odd number of times.

*   **Iteration**: We loop through each rectangle `[x1, y1, x2, y2]` once:
    1.  Update `minX`, `minY`, `maxX`, `maxY` with the coordinates of the current rectangle.
    2.  Add the area `(x2 - x1) * (y2 - y1)` to a running total.
    3.  Process the four corner points: `(x1, y1)`, `(x1, y2)`, `(x2, y1)`, and `(x2, y2)`. For each point, we 'toggle' its presence in our `HashSet`. To use a `Point` object in a `HashSet`, we need to properly implement `equals()` and `hashCode()`. A simpler way is to represent each point as a string, e.g., `"x,y"`.

*   **Verification**: After the loop, we perform two final checks:
    1.  **Area Check**: Calculate the area of the bounding box: `(maxX - minX) * (maxY - minY)`. This must be equal to the total area of the small rectangles we summed up. If not, it implies there's an overlap (summed area is too large) or a gap (summed area is too small).
    2.  **Corner Check**: The `HashSet` should contain exactly four points. These four points must be the corners of the bounding box we found: `(minX, minY)`, `(minX, maxY)`, `(maxX, minY)`, and `(maxX, maxY)`. If the set size is not 4, or if it contains any other points, it means some internal corners didn't cancel out, indicating an overlap or an imperfect tiling.

If both conditions are met, the rectangles form a perfect cover.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0) {
            return false;
        }

        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int maxY = Integer.MIN_VALUE;

        long totalArea = 0;
        Set<String> cornerPoints = new HashSet<>();

        for (int[] rect : rectangles) {
            int x1 = rect[0];
            int y1 = rect[1];
            int x2 = rect[2];
            int y2 = rect[3];

            // Update bounding box coordinates
            minX = Math.min(minX, x1);
            minY = Math.min(minY, y1);
            maxX = Math.max(maxX, x2);
            maxY = Math.max(maxY, y2);

            // Calculate and sum the area
            totalArea += (long)(x2 - x1) * (long)(y2 - y1);

            // Four corner points of the current rectangle
            String p1 = x1 + "," + y1;
            String p2 = x1 + "," + y2;
            String p3 = x2 + "," + y1;
            String p4 = x2 + "," + y2;

            // Toggle the presence of each corner point in the set
            if (!cornerPoints.add(p1)) cornerPoints.remove(p1);
            if (!cornerPoints.add(p2)) cornerPoints.remove(p2);
            if (!cornerPoints.add(p3)) cornerPoints.remove(p3);
            if (!cornerPoints.add(p4)) cornerPoints.remove(p4);
        }

        // 1. Area Check
        long expectedArea = (long)(maxX - minX) * (long)(maxY - minY);
        if (totalArea != expectedArea) {
            return false;
        }

        // 2. Corner Check
        if (cornerPoints.size() != 4) {
            return false;
        }

        // Check if the remaining points are the corners of the bounding box
        if (!cornerPoints.contains(minX + "," + minY)) return false;
        if (!cornerPoints.contains(minX + "," + maxY)) return false;
        if (!cornerPoints.contains(maxX + "," + minY)) return false;
        if (!cornerPoints.contains(maxX + "," + maxY)) return false;

        return true;
    }
}
```
### Algorithm
*   Initialize `totalArea = 0`, bounding box coordinates to extreme values, and an empty `HashSet` for corner points.
*   Iterate through each rectangle `[x1, y1, x2, y2]`:
    *   Update the bounding box coordinates (`minX`, `minY`, `maxX`, `maxY`).
    *   Add the rectangle's area to `totalArea`.
    *   For each of the four corner points, toggle its presence in the `HashSet`. (If it's present, remove it; if not, add it).
*   After the loop, calculate the `expectedArea` from the final bounding box coordinates.
*   Return `true` only if `totalArea` equals `expectedArea` AND the `HashSet` contains exactly the four corners of the bounding box.

# Solutions
### Java

```java
class Solution {
public
  boolean isRectangleCover(int[][] rectangles) {
    long area = 0;
    int minX = rectangles[0][0], minY = rectangles[0][1];
    int maxX = rectangles[0][2], maxY = rectangles[0][3];
    Map<Pair, Integer> cnt = new HashMap<>();
    for (int[] r : rectangles) {
      area += (r[2] - r[0]) * (r[3] - r[1]);
      minX = Math.min(minX, r[0]);
      minY = Math.min(minY, r[1]);
      maxX = Math.max(maxX, r[2]);
      maxY = Math.max(maxY, r[3]);
      cnt.merge(new Pair(r[0], r[1]), 1, Integer : : sum);
      cnt.merge(new Pair(r[0], r[3]), 1, Integer : : sum);
      cnt.merge(new Pair(r[2], r[3]), 1, Integer : : sum);
      cnt.merge(new Pair(r[2], r[1]), 1, Integer : : sum);
    }
    if (area != (long)(maxX - minX) * (maxY - minY) ||
        cnt.getOrDefault(new Pair(minX, minY), 0) != 1 ||
        cnt.getOrDefault(new Pair(minX, maxY), 0) != 1 ||
        cnt.getOrDefault(new Pair(maxX, maxY), 0) != 1 ||
        cnt.getOrDefault(new Pair(maxX, minY), 0) != 1) {
      return false;
    }
    cnt.remove(new Pair(minX, minY));
    cnt.remove(new Pair(minX, maxY));
    cnt.remove(new Pair(maxX, maxY));
    cnt.remove(new Pair(maxX, minY));
    return cnt.values().stream().allMatch(c->c == 2 || c == 4);
  }
private
  static class Pair {
    final int first;
    final int second;
    Pair(int first, int second) {
      this.first = first;
      this.second = second;
    }
    @Override public boolean equals(Object o) {
      if (this == o) {
        return true;
      }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }
      Pair pair = (Pair)o;
      return first == pair.first && second == pair.second;
    }
    @Override public int hashCode() {
      return Objects.hash(first, second);
    }
  }
}

```

### CPP

```cpp
#include <bits/stdc++.h> using namespace std ; class Solution { public: bool isRectangleCover ( vector < vector < int >>& rectangles ) { long long area = 0 ; int minX = rectangles [ 0 ][ 0 ], minY = rectangles [ 0 ][ 1 ]; int maxX = rectangles [ 0 ][ 2 ], maxY = rectangles [ 0 ][ 3 ]; using pii = pair < int , int > ; map < pii , int > cnt ; for ( auto & r : 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 ]}]; ++ cnt [{ r [ 0 ], r [ 3 ]}]; ++ cnt [{ r [ 2 ], r [ 3 ]}]; ++ cnt [{ r [ 2 ], r [ 1 ]}]; } if ( area != ( long long ) ( maxX - minX ) * ( maxY - minY ) || cnt [{ minX , minY }] != 1 || cnt [{ minX , maxY }] != 1 || cnt [{ maxX , maxY }] != 1 || cnt [{ maxX , minY }] != 1 ) { return false ; } cnt . erase ({ minX , minY }); cnt . erase ({ minX , maxY }); cnt . erase ({ maxX , maxY }); cnt . erase ({ maxX , minY }); return all_of ( cnt . begin (), cnt . end (), []( pair < pii , int > e ) { return e . second == 2 || e . second == 4 ; }); } };
```

### Python

```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())

```