391. Perfect Rectangle – Leetcode Solutions

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.

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        # Variables to store the total area and the extreme bounds of the rectangle
        total_area = 0
        min_x, min_y = float('inf'), float('inf')
        max_x, max_y = float('-inf'), float('-inf')
        
        # Set to track unique corners
        corners = set()

        # Loop through each rectangle to update bounds and area
        for x, y, a, b in rectangles:
            # Update the bounding rectangle
            min_x = min(min_x, x)
            min_y = min(min_y, y)
            max_x = max(max_x, a)
            max_y = max(max_y, b)
            
            # Calculate area of the current rectangle and add to total area
            total_area += (a - x) * (b - y)
            
            # Define the four corners of the current rectangle
            current_corners = [(x, y), (x, b), (a, y), (a, b)]
            
            # Process each corner: add if new, remove if already in the set
            for corner in current_corners:
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)
        
        # Calculate the area of the bounding rectangle
        bounding_area = (max_x - min_x) * (max_y - min_y)

        # Check conditions:
        # 1. Total area should match the bounding rectangle area
        # 2. Only four corners should remain in the set, and they should match the corners of the bounding rectangle
        expected_corners = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
        return total_area == bounding_area and corners == expected_corners

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        // Step 1: Initialize variables to track the area and corners
        int minX = INT_MAX, minY = INT_MAX, maxX = INT_MIN, maxY = INT_MIN;
        long totalArea = 0;
        
        // Using a set to track the corners of each rectangle
        set<pair<int, int>> corners;

        for (const auto& rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            
            // Step 2: Update the overall bounding box (minX, minY) to (maxX, maxY)
            minX = min(minX, x1);
            minY = min(minY, y1);
            maxX = max(maxX, x2);
            maxY = max(maxY, y2);

            // Step 3: Calculate the area of the current rectangle and add it to totalArea
            totalArea += (long)(x2 - x1) * (y2 - y1);

            // Step 4: Toggle corners in the set (if present, remove; if absent, add)
            pair<int, int> corner1 = {x1, y1};
            pair<int, int> corner2 = {x1, y2};
            pair<int, int> corner3 = {x2, y1};
            pair<int, int> corner4 = {x2, y2};

            for (const auto& corner : {corner1, corner2, corner3, corner4}) {
                if (corners.count(corner)) {
                    corners.erase(corner);
                } else {
                    corners.insert(corner);
                }
            }
        }

        // Step 5: Calculate the expected area of the bounding box and compare it with totalArea
        long expectedArea = (long)(maxX - minX) * (maxY - minY);
        if (totalArea != expectedArea) {
            return false;
        }

        // Step 6: Check if the corners set has exactly four corners of the bounding box
        if (corners.size() != 4 || 
            !corners.count({minX, minY}) || 
            !corners.count({minX, maxY}) || 
            !corners.count({maxX, minY}) || 
            !corners.count({maxX, maxY})) {
            return false;
        }

        return true;
    }
};

var isRectangleCover = function(rectangles) {
    // Variables to track the bounding rectangle's extreme points
    let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
    let actualArea = 0;

    // Set to track each unique corner point
    const pointSet = new Set();

    // Helper function to create a unique string key for each point
    const getPointKey = (x, y) => `${x},${y}`;

    for (let [x, y, a, b] of rectangles) {
        // Update bounding rectangle limits
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, a);
        maxY = Math.max(maxY, b);

        // Accumulate the area of each rectangle
        actualArea += (a - x) * (b - y);

        // Toggle each corner point in the set
        const corners = [
            [x, y],   // Bottom-left
            [x, b],   // Top-left
            [a, y],   // Bottom-right
            [a, b]    // Top-right
        ];

        for (let [px, py] of corners) {
            const pointKey = getPointKey(px, py);
            if (pointSet.has(pointKey)) {
                pointSet.delete(pointKey);
            } else {
                pointSet.add(pointKey);
            }
        }
    }

    // Calculate the expected area of the bounding rectangle
    const expectedArea = (maxX - minX) * (maxY - minY);

    // Check if the areas match and if only the four corners of the bounding rectangle remain
    if (actualArea !== expectedArea || pointSet.size !== 4) return false;

    // Verify that the remaining points in the set are the bounding rectangle's corners
    const expectedCorners = [
        getPointKey(minX, minY), // Bottom-left
        getPointKey(minX, maxY), // Top-left
        getPointKey(maxX, minY), // Bottom-right
        getPointKey(maxX, maxY)  // Top-right
    ];

    for (let corner of expectedCorners) {
        if (!pointSet.has(corner)) return false;
    }

    return true;
};

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        // Initialize variables to store the bounds of the overall rectangle
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int maxY = Integer.MIN_VALUE;

        // Track the total area of all rectangles
        int totalArea = 0;

        // Use a set to track unique corner points of the rectangles
        Set<String> corners = new HashSet<>();

        for (int[] rect : rectangles) {
            int x1 = rect[0], y1 = rect[1]; // Bottom-left corner
            int x2 = rect[2], y2 = rect[3]; // Top-right corner

            // Update the overall bounds
            minX = Math.min(minX, x1);
            minY = Math.min(minY, y1);
            maxX = Math.max(maxX, x2);
            maxY = Math.max(maxY, y2);

            // Calculate area of current rectangle and add to total area
            int area = (x2 - x1) * (y2 - y1);
            totalArea += area;

            // Define the four corners as strings to track their uniqueness
            String[] points = {
                x1 + " " + y1, // Bottom-left
                x1 + " " + y2, // Top-left
                x2 + " " + y1, // Bottom-right
                x2 + " " + y2  // Top-right
            };

            // For each corner, toggle its presence in the set
            for (String point : points) {
                if (!corners.add(point)) {
                    corners.remove(point); // Remove if it already exists
                }
            }
        }

        // Calculate the expected area of the large rectangle that should encompass all small rectangles
        int expectedArea = (maxX - minX) * (maxY - minY);

        // Check if total area matches the expected area of the large rectangle
        if (totalArea != expectedArea) {
            return false;
        }

        // Verify that only the four corners of the large rectangle remain in the set
        if (corners.size() != 4 || 
            !corners.contains(minX + " " + minY) ||
            !corners.contains(minX + " " + maxY) ||
            !corners.contains(maxX + " " + minY) ||
            !corners.contains(maxX + " " + maxY)) {
            return false;
        }

        return true;
    }
}