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.

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.

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.

Solution Implementation

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 using problem constraints.