Perfect Rectangle - Leetcode Solution

The Perfect Rectangle problem asks us to determine if a given set of rectangles can be rearranged into a perfect rectangle without overlapping. The perfect rectangle is defined as having a total area equal to the sum of all rectangles and having no gaps or overlaps. If we can rearrange the rectangles into a perfect rectangle, return true. Otherwise, return false.

To solve this problem, we can follow the below algorithm:

1. Calculate the total area of all the rectangles and the minimum and maximum coordinates of the rectangles.
2. Check if the total area of all the rectangles matches the area of the perfect rectangle. If not, return false.
3. Check that the minimum and maximum coordinates of the rectangles match the corners of the perfect rectangle. If not, return false.
4. Iterate through all the rectangles and mark the points that make up the edges of the rectangles.
5. Check that the marked points form a connected boundary around the perfect rectangle. If not, return false.
6. If all the above checks pass, return true.

Let's implement this approach step by step:

Step 1:

Calculate the total area of all the rectangles and the minimum and maximum coordinates of the rectangles.

class Solution: def isRectangleCover(self, rectangles: List[List[int]]) -> bool: area = 0 x1, y1, x2, y2 = float('inf'), float('inf'), float('-inf'), float('-inf') for rectangle in rectangles: x1, y1 = min(x1, rectangle[0]), min(y1, rectangle[1]) x2, y2 = max(x2, rectangle[2]), max(y2, rectangle[3]) area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1])

        if area != (x2 - x1) * (y2 - y1):
            return False
        return True

Step 2:

Check if the total area of all the rectangles matches the area of the perfect rectangle. If not, return false.

if area != (x2 - x1) * (y2 - y1): return False

Step 3:

Check that the minimum and maximum coordinates of the rectangles match the corners of the perfect rectangle. If not, return false.

if rectangle[0], rectangle[1] != x1, y1 or rectangle[2], rectangle[3] != x2, y2: return False

Step 4:

Iterate through all the rectangles and mark the points that make up the edges of the rectangles.

s = set() for rectangle in rectangles: for point in [(rectangle[0], rectangle[1]), (rectangle[2], rectangle[3]), (rectangle[0], rectangle[3]), (rectangle[2], rectangle[1])]: if point in s: s.remove(point) else: s.add(point)

Step 5:

Check that the marked points form a connected boundary around the perfect rectangle. If not, return false.

if len(s) != 4 or (x1, y1) not in s or (x2, y2) not in s: return False

Step 6:

If all the above checks pass, return true.

return True

The final solution is:

class Solution: def isRectangleCover(self, rectangles: List[List[int]]) -> bool: area = 0 x1, y1, x2, y2 = float('inf'), float('inf'), float('-inf'), float('-inf') s = set() for rectangle in rectangles: x1, y1 = min(x1, rectangle[0]), min(y1, rectangle[1]) x2, y2 = max(x2, rectangle[2]), max(y2, rectangle[3]) area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]) if rectangle[0], rectangle[1] != x1, y1 or rectangle[2], rectangle[3] != x2, y2: return False for point in [(rectangle[0], rectangle[1]), (rectangle[2], rectangle[3]), (rectangle[0], rectangle[3]), (rectangle[2], rectangle[1])]: if point in s: s.remove(point) else: s.add(point) if area != (x2 - x1) * (y2 - y1) or len(s) != 4 or (x1, y1) not in s or (x2, y2) not in s: return False return True

Time complexity: O(nlogn), where n is the number of rectangles. Space complexity: O(n).

1