Problem Description

Given a list of axis-aligned rectangles represented as arrays [x1, y1, x2, y2], where (x1, y1) is the bottom-left and (x2, y2) is the top-right corner, determine if they together form an exact cover of a rectangular region.

• Each rectangle's sides are parallel to the axes.
• The rectangles may overlap, touch, or be disjoint.
• Your goal is to check if all rectangles together exactly form one perfect rectangle, with no overlaps or gaps.
• Each rectangle must be used exactly once; you cannot reuse or ignore any rectangles.

Return True if the rectangles form a perfect rectangle, otherwise False.

Thought Process

At first glance, you might think to check every pair of rectangles for overlap or gaps, but this quickly becomes inefficient as the number of rectangles increases. Brute-force would mean checking every possible rectangle pair, which is slow and hard to implement.

Instead, let's consider what makes a set of rectangles form a perfect rectangle:

• The total area covered by all rectangles should be equal to the area of the bounding rectangle formed by the outermost edges.
• There should be no overlaps or gaps: each interior point should be covered exactly once.
• At the outer corners, each should appear exactly once; all other corners should appear an even number of times (shared by adjacent rectangles).

This leads us to a more efficient approach: use area calculation and track all corners using a set or map, focusing on the unique corners of the overall rectangle.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Find the bounding rectangle:
   • Iterate through all rectangles to find the minimum x1, y1 (bottom-left) and maximum x2, y2 (top-right). This defines the "perfect" rectangle we expect to form.
2. Sum up all areas:
   • For each rectangle, compute its area and add it to a running total.
   • At the end, this total should match the area of the bounding rectangle if there are no overlaps or gaps.
3. Track all corners using a set:
   • For each rectangle, note its four corners: (x1, y1), (x1, y2), (x2, y1), (x2, y2).
   • Add each corner to a set if it's not there; remove it if it is. This way, corners shared by multiple rectangles (i.e., internal corners) will cancel out, leaving only the four corners of the overall rectangle.
4. Final checks:
   • After processing, the set should contain exactly four points: the corners of the bounding rectangle.
   • The total area of all rectangles should equal the area of the bounding rectangle.

We use a set for corners because insertion and removal are O(1) operations, making the solution efficient.

Example Walkthrough

Suppose the input rectangles are:

• [1,1,3,3]
• [3,1,4,2]
• [3,2,4,4]
• [1,3,2,4]
• [2,3,3,4]

Let's trace the solution:

1. Find bounding rectangle: min x1=1, min y1=1, max x2=4, max y2=4. So the bounding rectangle is [1,1,4,4].
2. Sum areas:
   • [1,1,3,3]: area = 4
   • [3,1,4,2]: area = 1
   • [3,2,4,4]: area = 2
   • [1,3,2,4]: area = 1
   • [2,3,3,4]: area = 1

   Total area = 4+1+2+1+1 = 9

   Bounding rectangle area = (4-1)*(4-1) = 9

3. Track corners:
   • Add/remove each corner; after all rectangles, only the four corners (1,1), (1,4), (4,1), (4,4) remain in the set.
4. Final check: Areas match, and corners set size is 4 with correct points. Thus, the rectangles form a perfect rectangle.

Code Implementation

class Solution:
    def isRectangleCover(self, rectangles):
        min_x = min(rect[0] for rect in rectangles)
        min_y = min(rect[1] for rect in rectangles)
        max_x = max(rect[2] for rect in rectangles)
        max_y = max(rect[3] for rect in rectangles)
        
        area = 0
        corners = set()
        
        for x1, y1, x2, y2 in rectangles:
            area += (x2 - x1) * (y2 - y1)
            for corner in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:
                if corner in corners:
                    corners.remove(corner)
                else:
                    corners.add(corner)
        
        expected_area = (max_x - min_x) * (max_y - min_y)
        expected_corners = set([
            (min_x, min_y), (min_x, max_y),
            (max_x, min_y), (max_x, max_y)
        ])
        
        return area == expected_area and corners == expected_corners
      

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int min_x = INT_MAX, min_y = INT_MAX, max_x = INT_MIN, max_y = INT_MIN;
        set<pair<int, int>> corners;
        long area = 0;
        for (auto& rect : rectangles) {
            min_x = min(min_x, rect[0]);
            min_y = min(min_y, rect[1]);
            max_x = max(max_x, rect[2]);
            max_y = max(max_y, rect[3]);
            area += (long)(rect[2] - rect[0]) * (rect[3] - rect[1]);
            pair<int, int> pts[4] = {
                {rect[0], rect[1]}, {rect[0], rect[3]},
                {rect[2], rect[1]}, {rect[2], rect[3]}
            };
            for (auto& p : pts) {
                if (corners.count(p)) corners.erase(p);
                else corners.insert(p);
            }
        }
        long expected = (long)(max_x - min_x) * (max_y - min_y);
        set<pair<int, int>> expected_corners = {
            {min_x, min_y}, {min_x, max_y}, {max_x, min_y}, {max_x, max_y}
        };
        return area == expected && corners == expected_corners;
    }
};
      

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
        Set<String> corners = new HashSet<>();
        int area = 0;
        for (int[] rect : rectangles) {
            minX = Math.min(minX, rect[0]);
            minY = Math.min(minY, rect[1]);
            maxX = Math.max(maxX, rect[2]);
            maxY = Math.max(maxY, rect[3]);
            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
            String[] pts = {
                rect[0] + " " + rect[1],
                rect[0] + " " + rect[3],
                rect[2] + " " + rect[1],
                rect[2] + " " + rect[3]
            };
            for (String p : pts) {
                if (!corners.add(p)) corners.remove(p);
            }
        }
        int expected = (maxX - minX) * (maxY - minY);
        Set<String> expectedCorners = new HashSet<>();
        expectedCorners.add(minX + " " + minY);
        expectedCorners.add(minX + " " + maxY);
        expectedCorners.add(maxX + " " + minY);
        expectedCorners.add(maxX + " " + maxY);
        return area == expected && corners.equals(expectedCorners);
    }
}
      

var isRectangleCover = function(rectangles) {
    let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
    let area = 0;
    let corners = new Set();
    for (let rect of rectangles) {
        minX = Math.min(minX, rect[0]);
        minY = Math.min(minY, rect[1]);
        maxX = Math.max(maxX, rect[2]);
        maxY = Math.max(maxY, rect[3]);
        area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
        let pts = [
            rect[0] + ',' + rect[1],
            rect[0] + ',' + rect[3],
            rect[2] + ',' + rect[1],
            rect[2] + ',' + rect[3]
        ];
        for (let p of pts) {
            if (corners.has(p)) corners.delete(p);
            else corners.add(p);
        }
    }
    let expected = (maxX - minX) * (maxY - minY);
    let expectedCorners = new Set([
        minX + ',' + minY,
        minX + ',' + maxY,
        maxX + ',' + minY,
        maxX + ',' + maxY
    ]);
    if (area !== expected) return false;
    if (corners.size !== 4) return false;
    for (let p of expectedCorners) {
        if (!corners.has(p)) return false;
    }
    return true;
};
      

Time and Space Complexity

Brute-force approach:

• Would require checking every pair of rectangles for overlaps and gaps, leading to O(N²) time complexity (where N is the number of rectangles).
• Space complexity would also be high if tracking all covered points or regions.

• We process each rectangle once, so time complexity is O(N).
• For each rectangle, we do a constant amount of work (area calculation and up to 4 corner insertions/removals).
• Space complexity is O(N) in the worst case for the corners set, but in practice, it’s at most 4 for a perfect rectangle.

Thus, the optimized solution is highly efficient compared to brute-force.

Summary

The key insight is that a perfect rectangle cover requires both area matching and exactly four unique corners (the outermost corners). By tracking areas and using a set to manage corners, we elegantly avoid dealing with complex overlap/gap checks. This approach is efficient, easy to implement, and leverages set operations for correctness.