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

Rectangle Area II

Difficulty: Hard

Problem Description

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the i-th rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner. Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once. Return the total area modulo 10^9 + 7.

Key Insights

  • The problem requires calculating the union area of multiple rectangles, which can overlap.
  • A line sweep algorithm can be employed to efficiently compute the area by processing events corresponding to the edges of the rectangles.
  • Utilizing data structures such as segment trees or ordered sets can help maintain the active intervals during the sweep.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of rectangles due to sorting the events and maintaining active intervals. Space Complexity: O(n) for storing the events and active intervals.

Solution

To solve this problem, we use a line sweep algorithm. We treat the left and right edges of the rectangles as events. As we sweep from left to right, we keep track of the active intervals (y-coordinates) that are currently covered by rectangles. We can use a segment tree or an ordered set to efficiently manage these intervals. The area can be computed by multiplying the width of the sweep by the total height covered by the active intervals.

Code Solutions

def rectangleArea(rectangles):
    MOD = 10**9 + 7
    events = []
    for x1, y1, x2, y2 in rectangles:
        events.append((x1, y1, y2, 1))  # Start of rectangle
        events.append((x2, y1, y2, -1)) # End of rectangle
    
    # Sort events: primarily by x, then by type (start before end)
    events.sort()
    
    def calculate_height(active_intervals):
        total_height = 0
        current_start = -1
        current_count = 0
        
        for y1, y2 in sorted(active_intervals):
            if current_count > 0:
                total_height += max(0, min(y2, current_end) - max(y1, current_start))
            if current_start < y1:
                current_start = y1
                current_end = y2
                current_count = 1
            else:
                current_end = max(current_end, y2)
                current_count += 1
        
        return total_height
    
    total_area = 0
    active_intervals = []
    prev_x = events[0][0]
    
    for x, y1, y2, typ in events:
        height = calculate_height(active_intervals)
        total_area += height * (x - prev_x) % MOD
        total_area %= MOD
        if typ == 1:
            active_intervals.append((y1, y2))
        else:
            active_intervals.remove((y1, y2))
        prev_x = x

    return total_area
← Back to All Questions