{x}
blog image

Perfect Rectangle

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

 

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.

 

Constraints:

  • 1 <= rectangles.length <= 2 * 104
  • rectangles[i].length == 4
  • -105 <= xi < ai <= 105
  • -105 <= yi < bi <= 105

Solution Explanation

This problem asks whether a set of rectangles perfectly covers a larger rectangular region without any overlaps or gaps. The solution uses a clever approach that leverages the properties of a perfect rectangular cover.

Core Idea:

  1. Total Area: Calculate the total area of all input rectangles. If this doesn't match the area of the bounding rectangle (formed by the minimum and maximum x and y coordinates), then it's not a perfect cover.

  2. Corner Points: Count how many times each corner point (x, y) appears across all rectangles. For a perfect cover, the four corner points of the bounding rectangle should each appear exactly once. All other points must appear an even number of times (2 or 4) because each internal point must belong to exactly two rectangles.

Algorithm:

  1. Initialization:

    • area: Initialize to 0. This will accumulate the total area of all rectangles.
    • minX, minY, maxX, maxY: Initialize to the coordinates of the first rectangle. These will track the boundaries of the overall rectangular region.
    • cnt: A dictionary (or hash map) to store the count of each corner point.

  2. Iterate Through Rectangles:

    • For each rectangle [x, y, a, b]:
      • Add its area (a - x) * (b - y) to area.
      • Update minX, minY, maxX, maxY to reflect the overall boundaries.
      • Increment the count of the four corner points (x, y), (x, b), (a, b), (a, y) in the cnt dictionary.

  3. Check Total Area and Corner Points:

    • Verify that the total area equals the area of the bounding rectangle (maxX - minX) * (maxY - minY). If not, return false.
    • Check if the four corner points of the bounding rectangle ((minX, minY), (minX, maxY), (maxX, maxY), (maxX, minY)) each appear exactly once in cnt. If not, return false.

  4. Check Internal Points:

    • Remove the four corner points of the bounding rectangle from cnt.
    • Iterate through the remaining entries in cnt. For each point, check if its count is either 2 or 4 (even number). If any point has an odd count, it indicates an overlap or gap, so return false.

  5. Return true: If all checks pass, it means the rectangles form a perfect cover.

Time Complexity: O(N), where N is the number of rectangles. The algorithm iterates through the rectangles once to calculate the area and count corner points. The subsequent checks take constant time relative to N.

Space Complexity: O(N) in the worst case, because the cnt dictionary can potentially store all the unique corner points. In practice, it usually stores far fewer points because many corners overlap.

Code Explanations (Python3, Java, C++, Go):

The provided code in all four languages directly implements the algorithm described above. The core logic is the same across all versions; only the syntax and data structures differ. Noteworthy elements include the use of dictionaries/maps to store corner point counts and the efficient handling of corner point counts. Error handling ensures that all the necessary conditions for a perfect rectangle are verified.