LeetCode Solutions Blog

Rectangle Area II

Number: 880

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given multiple axis‐aligned rectangles (each specified by the bottom-left and top-right coordinates), compute the total area covered by these rectangles (i.e. the union of all rectangle areas). Since rectangles may overlap, any overlapping area should be counted only once. Return the computed area modulo 10^9+7.

Key Insights

Use a line sweep algorithm along the x-axis to break the problem into vertical slices.
For each vertical slice, compute the union of the active y-intervals.
Apply coordinate compression on the y-values since they can be very large.
Utilize a segment tree (or an equivalent data structure) to efficiently track and update the length of y-intervals that are currently active.
Process two event types per rectangle: one when entering (adding a y-interval) and one when leaving (removing a y-interval).

Space and Time Complexity

Time Complexity: O(n log n) – sorting events and processing them using the segment tree. Space Complexity: O(n) – for storing events, the list of unique y-coordinates, and the segment tree structure.

Solution

The solution involves sweeping a vertical line across the x-axis and handling events where a rectangle starts or ends. For each rectangle, generate two events: one for adding the corresponding y-interval when the sweep line hits the left edge, and one for removing the interval when hitting the right edge. The y-coordinates are compressed to allow efficient segment tree operations. The segment tree keeps track of the coverage count and the total covered length on the y-axis. For each segment between consecutive x-values, multiply the width of the segment (delta in x) by the current union length of y-intervals to accumulate the area. Finally, return the accumulated area modulo 10^9+7.

Code Solutions

# Python solution using segment tree with coordinate compression

MOD = 10**9 + 7

# Helper function to build and update the segment tree
class SegmentTree:
    def __init__(self, ys):
        self.ys = ys  # sorted unique y values
        self.n = len(ys) - 1  # intervals count
        # count: how many times a segment is covered
        # length: the total covered length in that segment
        self.count = [0] * (4 * self.n)
        self.length = [0] * (4 * self.n)
    
    def update(self, idx, left, right, ql, qr, val):
        if ql >= right or qr <= left:  # no overlap
            return
        if ql <= left and right <= qr:  # total overlap
            self.count[idx] += val
        else:
            mid = (left + right) // 2
            self.update(idx * 2, left, mid, ql, qr, val)
            self.update(idx * 2 + 1, mid, right, ql, qr, val)
        
        if self.count[idx] > 0:
            # If count > 0, entire interval is covered
            self.length[idx] = self.ys[right] - self.ys[left]
        else:
            if right - left == 1:
                self.length[idx] = 0
            else:
                self.length[idx] = self.length[idx * 2] + self.length[idx * 2 + 1]
                
def rectangleArea(rectangles):
    events = []
    ys = set()
    # Prepare events and collect y values for compression
    for x1, y1, x2, y2 in rectangles:
        events.append((x1, y1, y2, 1))   # entering event
        events.append((x2, y1, y2, -1))  # leaving event
        ys.add(y1)
        ys.add(y2)
    
    # Sort unique y coordinates and events by x-coordinate
    ys = sorted(ys)
    events.sort()
    
    st = SegmentTree(ys)
    prev_x = events[0][0]
    area = 0
    for x, y1, y2, typ in events:
        dx = x - prev_x
        # st.length[1] holds the total covered length in the y direction
        area = (area + dx * st.length[1]) % MOD
        # Find indices for y1 and y2 in the compressed list
        left = ys.index(y1)
        right = ys.index(y2)
        st.update(1, 0, st.n, left, right, typ)
        prev_x = x
    return area

# Example usage:
# print(rectangleArea([[0,0,2,2],[1,0,2,3],[1,0,3,1]]))