391. Perfect Rectangle


Problem Description

The problem presents us with multiple axis-aligned rectangles, each represented by a list of four integers. These integers, [x_i, y_i, a_i, b_i], define the coordinates of the bottom-left (x_i, y_i) and the top-right (a_i, b_i) points of rectangle i. The task is to determine whether these rectangles, when combined, form a perfect cover for some rectangular region without any overlaps or gaps. In other words, we need to check if the rectangles together exactly fill a larger rectangle.

To solve this problem, we would check that the combined area of the small rectangles matches the area of the bounding rectangle, which is defined by the smallest and largest x and y coordinates from all rectangles. In addition, we must also ensure that each corner of the bounding rectangle belongs to exactly one rectangle (for a perfect fit), and all other vertices must be shared by either two or four rectangles (as they would be on the edges or inside the shape).

Intuition

The solution leverages geometry and hash mapping to verify two conditions:

  1. Area Condition: The sum of areas of all small rectangles must equal the area of the bounding rectangle. To do this, we iterate over all the rectangles, calculate their individual areas, and sum them up. Simultaneously, we record the minimum and maximum x and y coordinates to identify the bounding rectangle. The area of the bounding rectangle is then compared with the summed area of all small rectangles.

  2. Vertex Condition: A rectangle's corner points appear in a certain pattern: each corner of the bounding rectangle should only appear once among all rectangles (the corners of our desired larger rectangle), and other points should appear either two or four times. Points that appear once (other than the corners of the bounding rectangle) or an odd number of times would indicate gaps or overlaps.

    • We use a defaultdict(int) to count the appearances of each vertex.
    • During iteration, we increment the count for each vertex of a rectangle.
    • After processing all rectangles and checking the Area Condition, we examine the vertices.
    • We remove the corners of the bounding rectangle and expect all remaining vertices to have counts of either 2 or 4.

By ensuring that both conditions are satisfied, we can confirm whether the rectangles form an exact cover of a rectangular region.

Learn more about Line Sweep patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The implementation of the solution involves the following steps and uses the defaultdict from the collections module of Python for efficient counting.

  1. Initialization and Area Calculation:

    • We start by initializing the variables minX, minY, maxX, and maxY with the respective values from the first rectangle. These variables will eventually define the bounding rectangle by keeping track of the minimum and maximum x and y coordinates encountered across all rectangles.
    • We also initialize a counter cnt using defaultdict(int) to keep a count of how often each vertex appears across all the rectangles.
    • In a loop over all the rectangles, we update
      • The total area by adding the area of each rectangle (calculated as (r[2] - r[0]) * (r[3] - r[1]) where r represents a rectangle).
      • The minX, minY, maxX, and maxY when we find a coordinate smaller or larger than the current recorded extremes.
      • The count of each vertex by incrementing their counts in the cnt dictionary.
  2. Area Condition Check:

    • After processing all rectangles, we check if the total area of all the small rectangles equals the area of the bounding rectangle. The area of the bounding rectangle is computed as (maxX - minX) * (maxY - minY).
  3. Corner Vertex Count Check:

    • We immediately check if each corner of the bounding rectangle exists exactly once in the vertex count map cnt. If not, we can conclude the rectangles do not form a perfect rectangular region and return False.
  4. Vertex Condition Check:

    • Before the final verification of the vertices, we remove the counts of the bounding rectangle corners from cnt.
    • We then proceed to check if all remaining counts in cnt have values that are either 2 or 4.
      • If a vertex count is not 2 or 4, it means there's either an overlap or a gap.
      • If all counts are 2 or 4, we conclude that the internal edges and vertices align perfectly without any gaps or overlaps.
  5. Return Value:

    • If both the conditions are met, we return True, indicating all rectangles form an exact cover of a rectangular region.

The algorithm efficiently processes the input by using a hashmap (implemented as defaultdict(int)), keeping track of the total area on-the-fly, and minimizing the number of checks during vertex count verification to those that are crucial for determining whether the rectangles form an exact cover.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's consider a set of rectangles represented by their bottom-left and top-right coordinates as follows:

Rectangle 1: [1, 1, 3, 3] Rectangle 2: [3, 1, 4, 2] Rectangle 3: [1, 3, 2, 4] Rectangle 4: [2, 2, 3, 4]

Step 1: Initialization and Area Calculation

We begin by initializing minX, minY, maxX, and maxY with values from the first rectangle, resulting in minX = 1, minY = 1, maxX = 3, maxY = 3.

We then use a defaultdict(int) to track the vertex appearances and start a total area count as area = 0.

Iterating over the rectangles:

  • For Rectangle 1, the area is (3 - 1) * (3 - 1) = 4. We update area to 4, and our vertex counts for points (1, 1), (1, 3), (3, 1), and (3, 3) increase by 1.
  • Rectangle 2 contributes an area of 1. The total area now is 5, and points (3, 1), (4, 1), (3, 2), and (4, 2) adjust counts accordingly.
  • Rectangle 3 adds an area of 1 to the total, which becomes 6. We update counts for (1, 3), (2, 3), (1, 4), and (2, 4).
  • For Rectangle 4, the area is 2, making the total area 8. We adjust our counts for (2, 2), (3, 2), (2, 4), and (3, 4).

During these updates, maxX is adjusted to 4, and maxY to 4.

Step 2: Area Condition Check

The area of the bounding rectangle is (maxX - minX) * (maxY - minY), which results in (4 - 1) * (4 - 1) = 9.

Comparing the bounding rectangle area of 9 with the total calculated area of 8, we find they do not match. Hence, the rectangles cannot perfectly cover the region.

In a case where the areas match, we would proceed to the next steps.

Step 3 and 4: Corner Vertex Count Check and Vertex Condition Check

If the total area matched, we would check that each corner of the bounding rectangle has a count of exactly 1 in our defaultdict. The corners would be (1, 1), (1, 4), (4, 1), and (4, 4).

For our counts, (1, 4) and (4, 1) would need to be exactly 1, failing which the rectangles do not form a perfect cover.

After ensuring that the corner vertices have the right count, removing them from our consideration, we would verify that all other vertices must have counts of 2 or 4.

Since our area did not match at Step 2, these would not be necessary to check in this example. However, these checks are crucial in cases where the areas computed are the same, as they rule out any overlaps or gaps within the covered area.

Step 5: Return Value

Given the discrepancy in the total and bounding rectangle areas, the algorithm would return False. If areas matched and all other vertex conditions were satisfied, the algorithm would return True.

Not Sure What to Study? Take the 2-min Quiz:

Which of these properties could exist for a graph but not a tree?

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def is_rectangle_cover(self, rectangles: List[List[int]]) -> bool:
5        # Initialize the area of rectangles and the points of the large enclosing rectangle
6        total_area = 0
7        min_x, min_y = rectangles[0][0], rectangles[0][1]
8        max_x, max_y = rectangles[0][2], rectangles[0][3]
9        # A dictionary to keep the count of how many times each corner appears
10        corner_count = defaultdict(int)
11
12        # Iterate through all rectangles to calculate total area and the points of the enclosing rectangle
13        for rect in rectangles:
14            # Calculate area of the current rectangle and add to total_area
15            total_area += (rect[2] - rect[0]) * (rect[3] - rect[1])
16          
17            # Update the coordinates of the enclosing rectangle
18            min_x = min(min_x, rect[0])
19            min_y = min(min_y, rect[1])
20            max_x = max(max_x, rect[2])
21            max_y = max(max_y, rect[3])
22
23            # Increment the count for each corner point of the current rectangle
24            corner_count[(rect[0], rect[1])] += 1
25            corner_count[(rect[0], rect[3])] += 1
26            corner_count[(rect[2], rect[3])] += 1
27            corner_count[(rect[2], rect[1])] += 1
28
29        # Check if the total area of the small rectangles equals the area of the enclosing rectangle
30        # and if each corner of the enclosing rectangle appears exactly once
31        if (total_area != (max_x - min_x) * (max_y - min_y) or
32                corner_count[(min_x, min_y)] != 1 or
33                corner_count[(min_x, max_y)] != 1 or
34                corner_count[(max_x, max_y)] != 1 or
35                corner_count[(max_x, min_y)] != 1):
36            return False
37
38        # Remove the corners of the enclosing rectangle from the count dictionary
39        del corner_count[(min_x, min_y)], corner_count[(min_x, max_y)], corner_count[(max_x, max_y)], corner_count[(max_x, min_y)]
40
41        # Check that all other corners appear exactly twice or four times 
42        # (they must be part of two or four rectangles respectively)
43        return all(count == 2 or count == 4 for count in corner_count.values())
44

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3import java.util.Objects;
4
5public class Solution {
6
7    public boolean isRectangleCover(int[][] rectangles) {
8        long totalArea = 0;
9        int minX = rectangles[0][0];
10        int minY = rectangles[0][1];
11        int maxX = rectangles[0][2];
12        int maxY = rectangles[0][3];
13        Map<Point, Integer> cornerCount = new HashMap<>();
14
15        // Calculate the total area and find the bounding rectangle coordinates
16        for (int[] rectangle : rectangles) {
17            totalArea += (long) (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
18
19            minX = Math.min(minX, rectangle[0]);
20            minY = Math.min(minY, rectangle[1]);
21            maxX = Math.max(maxX, rectangle[2]);
22            maxY = Math.max(maxY, rectangle[3]);
23
24            // Count how many times each corner appears across all rectangles
25            cornerCount.merge(new Point(rectangle[0], rectangle[1]), 1, Integer::sum);
26            cornerCount.merge(new Point(rectangle[0], rectangle[3]), 1, Integer::sum);
27            cornerCount.merge(new Point(rectangle[2], rectangle[3]), 1, Integer::sum);
28            cornerCount.merge(new Point(rectangle[2], rectangle[1]), 1, Integer::sum);
29        }
30
31        // Check if the total area of the rectangles matches the area of the bounding rectangle
32        // and if each corner of the bounding rectangle appears exactly once
33        if (totalArea != (long) (maxX - minX) * (maxY - minY)
34                || cornerCount.getOrDefault(new Point(minX, minY), 0) != 1
35                || cornerCount.getOrDefault(new Point(minX, maxY), 0) != 1 
36                || cornerCount.getOrDefault(new Point(maxX, maxY), 0) != 1 
37                || cornerCount.getOrDefault(new Point(maxX, minY), 0) != 1) {
38            return false;
39        }
40
41        // Remove the corners of the bounding rectangle from the corner count
42        cornerCount.remove(new Point(minX, minY));
43        cornerCount.remove(new Point(minX, maxY));
44        cornerCount.remove(new Point(maxX, maxY));
45        cornerCount.remove(new Point(maxX, minY));
46
47        // All other corners should appear either twice or four times
48        return cornerCount.values().stream().allMatch(count -> count == 2 || count == 4);
49    }
50
51    // Helper class to represent a point (corner) on the grid
52    private static class Point {
53        final int x;
54        final int y;
55
56        Point(int x, int y) {
57            this.x = x;
58            this.y = y;
59        }
60
61        @Override
62        public boolean equals(Object other) {
63            if (this == other) {
64                return true;
65            }
66            if (other == null || getClass() != other.getClass()) {
67                return false;
68            }
69            Point point = (Point) other;
70            return x == point.x && y == point.y;
71        }
72
73        @Override
74        public int hashCode() {
75            return Objects.hash(x, y);
76        }
77    }
78}
79

C++ Solution

1#include <algorithm> // For min/max functions
2#include <map>       // For map container
3#include <utility>   // For pair utility
4#include <vector>    // For vector container
5
6class Solution {
7public:
8    // Function to check if given rectangles form a perfect rectangle
9    bool isRectangleCover(std::vector<std::vector<int>>& rectangles) {
10        long long totalArea = 0;
11        int minX = rectangles[0][0], minY = rectangles[0][1];
12        int maxX = rectangles[0][2], maxY = rectangles[0][3];
13
14        // Define a type alias for a point (or vertex)
15        using Point = std::pair<int, int>;
16        // Map to count the occurrences of each point
17        std::map<Point, int> pointCount;
18
19        // Iterate over the rectangles to calculate the total area
20        // and find the bounding box of the large rectangle
21        for (auto& rect : rectangles) {
22            // Calculate the area of current rectangle
23            totalArea += static_cast<long long>(rect[2] - rect[0]) * (rect[3] - rect[1]);
24
25            // Update the bounding box corners
26            minX = std::min(minX, rect[0]);
27            minY = std::min(minY, rect[1]);
28            maxX = std::max(maxX, rect[2]);
29            maxY = std::max(maxY, rect[3]);
30
31            // Increment the count of each corner for the current rectangle
32            ++pointCount[{rect[0], rect[1]}];
33            ++pointCount[{rect[0], rect[3]}];
34            ++pointCount[{rect[2], rect[3]}];
35            ++pointCount[{rect[2], rect[1]}];
36        }
37
38        // Check if the total area of the rectangles equals the area of the bounding box
39        // and that each corner of the bounding box occurs exactly once
40        if (totalArea != static_cast<long long>(maxX - minX) * (maxY - minY) ||
41            pointCount[{minX, minY}] != 1 || pointCount[{minX, maxY}] != 1 ||
42            pointCount[{maxX, maxY}] != 1 || pointCount[{maxX, minY}] != 1) {
43            return false;
44        }
45
46        // Erase the corners of the bounding box from our count map,
47        // as they should no longer be considered in the final condition
48        pointCount.erase({minX, minY});
49        pointCount.erase({minX, maxY});
50        pointCount.erase({maxX, maxY});
51        pointCount.erase({maxX, minY});
52
53        // Check the remaining points to make sure all occur in pairs or fours
54        // This ensures that all the internal edges (which must be shared by two rectangles) are covered
55        return std::all_of(pointCount.begin(), pointCount.end(), [](const std::pair<Point, int>& element) {
56            return element.second == 2 || element.second == 4;
57        });
58    }
59};
60

Typescript Solution

1// Importing Map from ES6 feature set for map container functionality
2import { Map } from 'es6-map';
3
4// Typing for a point
5type Point = [number, number];
6
7// Define a Map type alias for Point to number mapping
8type PointCount = Map<Point, number>;
9
10// Function to check if given rectangles form a perfect rectangle
11function isRectangleCover(rectangles: number[][]): boolean {
12    let totalArea: number = 0;
13    let minX: number = rectangles[0][0], minY: number = rectangles[0][1];
14    let maxX: number = rectangles[0][2], maxY: number = rectangles[0][3];
15
16    // Map to count occurrences of each point
17    const pointCount: PointCount = new Map<Point, number>();
18
19    // Iterate over the rectangles to calculate the total area and find the bounding box of the large rectangle
20    for (const rect of rectangles) {
21        // Calculate the area of current rectangle
22        totalArea += (rect[2] - rect[0]) * (rect[3] - rect[1]);
23
24        // Update the bounding box corners
25        minX = Math.min(minX, rect[0]);
26        minY = Math.min(minY, rect[1]);
27        maxX = Math.max(maxX, rect[2]);
28        maxY = Math.max(maxY, rect[3]);
29
30        // Increment the count of each corner for the current rectangle
31        incrementPointCount(pointCount, rect[0], rect[1]);
32        incrementPointCount(pointCount, rect[0], rect[3]);
33        incrementPointCount(pointCount, rect[2], rect[3]);
34        incrementPointCount(pointCount, rect[2], rect[1]);
35    }
36
37    // Check if the total area of the rectangles equals the area of the bounding box
38    // and that each corner of the bounding box occurs exactly once
39    const expectedArea = (maxX - minX) * (maxY - minY);
40    const corners = [[minX, minY], [minX, maxY], [maxX, maxY], [maxX, minY]];
41    if (totalArea != expectedArea || !corners.every(corner => pointCount.get(corner as Point) === 1)) {
42        return false;
43    }
44
45    // Remove the corners of the bounding box from point count map
46    for (const corner of corners) {
47        pointCount.delete(corner as Point);
48    }
49
50    // Check the remaining points to ensure all occur in pairs or fours
51    for (const [_, count] of pointCount) {
52        if (count !== 2 && count !== 4) {
53            return false;
54        }
55    }
56
57    // All checks passed, the rectangles form a perfect rectangle
58    return true;
59}
60
61// Helper function to increment point count in the map
62function incrementPointCount(pointCount: PointCount, x: number, y: number): void {
63    const point: Point = [x, y];
64    const count = pointCount.get(point) || 0;
65    pointCount.set(point, count + 1);
66}
67
Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

Time Complexity

The time complexity of the provided code chiefly comes from a few operations: looping through rectangles, calculating the area of each small rectangle, finding the min and max for x and y coordinates, and counting corners.

  1. Looping through each rectangle (for loop): This has a time complexity of O(N) where N is the number of rectangles.
  2. Area calculation for each rectangle: This is a constant time operation for each rectangle but since it is inside the loop, it doesn't add to the overall time complexity, so it remains O(N).
  3. Finding the minX, minY, maxX, and maxY is also done within the same loop, so this is also O(N).
  4. Updating the counter (cnt) for each corner of every rectangle: Since each rectangle has four corners and there are N rectangles, this would be done 4N times which is still in O(N) time complexity.
  5. After the loop, we have constant-time checks for the corners of the big rectangle formed by minX, minY, maxX, and maxY, which doesn't affect the overall time complexity.
  6. A final loop to ensure that all counts of points (that are not the 4 outer corners) are either 2 or 4 contributes an O(K) complexity, where K is the number of unique points. However, K can be at most 4N since each rectangle can add up to 4 unique points. Thus, this part is also O(N).

Considering all parts, the time complexity of the algorithm is O(N).

Space Complexity

The space complexity comes from storing the count of coordinates, the extreme values (minX, minY, maxX, maxY), and the complete area.

  1. Storing the counts (cnt): Since each rectangle contributes 4 points, and in the worst case all rectangles can be distinct, the number of entries in the "count" dictionary could be 4N. Hence, the space complexity is O(N).
  2. Storing minX, minY, maxX, and maxY: Since these are just four variables, they use O(1) space.
  3. Temporary variables used in checks and calculations are also O(1) space.

Therefore, the overall space complexity is O(N).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫