We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Perfect Rectangle

Difficulty: Hard

Problem Description

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.

Key Insights

  • The total area covered by the rectangles must equal the area of the bounding rectangle.
  • Each corner of the rectangles must appear an odd number of times (once for each rectangle that uses it) to ensure there are no overlaps or gaps.
  • A line sweep algorithm can be applied to check for overlaps and to track the coverage of rectangles.

Space and Time Complexity

Time Complexity: O(n log n) - for sorting the events and processing them. Space Complexity: O(n) - for storing the active intervals during the sweep.

Solution

To solve the problem, we can use the line sweep technique along with a hash map to count the occurrences of each corner. We first calculate the total area covered by all rectangles and the coordinates of the bounding rectangle. Then, we use a line sweep to ensure that all corners are properly accounted for without overlaps.

  1. Calculate the total area of all rectangles.
  2. Determine the bounding rectangle by finding the minimum and maximum x and y coordinates.
  3. Use a sweep line algorithm to track vertical edges of rectangles:
    • For each rectangle, add two events: one for the left edge (entering) and one for the right edge (exiting).
    • As we process these events, maintain a count of active intervals.
  4. Ensure that at each step, the current active intervals do not overlap and that they cover the expected height.

Code Solutions

def isRectangleCover(rectangles):
    from collections import defaultdict
    
    corner_count = defaultdict(int)
    total_area = 0
    min_x = min_y = float('inf')
    max_x = max_y = float('-inf')
    
    for x1, y1, x2, y2 in rectangles:
        total_area += (x2 - x1) * (y2 - y1)
        corner_count[(x1, y1)] += 1
        corner_count[(x1, y2)] += 1
        corner_count[(x2, y1)] += 1
        corner_count[(x2, y2)] += 1
        
        min_x = min(min_x, x1)
        min_y = min(min_y, y1)
        max_x = max(max_x, x2)
        max_y = max(max_y, y2)
    
    expected_area = (max_x - min_x) * (max_y - min_y)
    
    if total_area != expected_area:
        return False
    
    corners = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
    
    for corner, count in corner_count.items():
        if corner in corners and count != 1:
            return False
        elif corner not in corners and count % 2 != 0:
            return False

    return True
← Back to All Questions