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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Perfect Rectangle

Number: 391

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array of axis-aligned rectangles, where each rectangle is represented by its bottom-left point (x, y) and top-right point (a, b), determine if all the rectangles together form an exact cover of a rectangular region with no overlaps and no gaps.

Key Insights

  • Compute the overall bounding rectangle by taking the minimum x, minimum y, maximum a, and maximum b from all rectangles.
  • Sum the areas of all given rectangles; this should equal the area of the overall bounding rectangle.
  • Use a set to track all four corners of each rectangle. For each rectangle, add its four corners if they are seen for the first time and remove them if they appear again.
  • At the end, the set should contain exactly the four corners of the overall bounding rectangle. Any extra points indicate either overlapping or gaps.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rectangles, because we iterate through each rectangle exactly once. Space Complexity: O(n) in the worst-case scenario for storing corner points in the set.

Solution

The solution is based on two main observations. First, the total area of all small rectangles must equal the area of the overall bounding rectangle defined by the extreme coordinates. Second, by using a set to add and remove corner points of every rectangle, all internal points (which occur more than once) cancel out, leaving only the four corner points of the bounding rectangle. If the set does not exactly match these four corners, then the rectangles do not form a perfect cover.

Code Solutions

def isRectangleCover(rectangles):
    # Initialize bounding rectangle coordinates
    min_x = float('inf')
    min_y = float('inf')
    max_x = float('-inf')
    max_y = float('-inf')
    total_area = 0
    # Set to track all corners
    corners = set()
    
    for rect in rectangles:
        x, y, a, b = rect[0], rect[1], rect[2], rect[3]
        # Update overall bounding box
        min_x = min(min_x, x)
        min_y = min(min_y, y)
        max_x = max(max_x, a)
        max_y = max(max_y, b)
        # Calculate area of the current rectangle and add to total area
        total_area += (a - x) * (b - y)
        
        # List of current rectangle's corners
        current_corners = [(x, y), (x, b), (a, y), (a, b)]
        # Add or remove corners from the set
        for point in current_corners:
            if point in corners:
                corners.remove(point)
            else:
                corners.add(point)
    
    # Check if total area matches the area of the overall bounding rectangle
    expected_area = (max_x - min_x) * (max_y - min_y)
    if total_area != expected_area:
        return False
    
    # The set must contain exactly the four corners of the overall rectangle
    expected_corners = {(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)}
    return corners == expected_corners

# Example usage:
rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
print(isRectangleCover(rectangles))  # Output: True
← Back to All Questions