LeetCode 850 - Rectangle Area II

This problem asks us to compute the total area covered by a set of axis-aligned rectangles on a 2D plane. Each rectangle is defined by its bottom-left and top-right coordinates [xi1, yi1, xi2, yi2].

leetcodehardarraysegment-treesweep-lineordered-set

LeetCode Problem 850

Difficulty: 🔴 Hard
Topics: Array, Segment Tree, Sweep Line, Ordered Set

Solution

Problem Understanding

This problem asks us to compute the total area covered by a set of axis-aligned rectangles on a 2D plane. Each rectangle is defined by its bottom-left and top-right coordinates [xi1, yi1, xi2, yi2]. The challenge is that rectangles can overlap, and any overlapping region must only be counted once. The final area must be returned modulo 10^9 + 7 due to potential large results.

The input rectangles is a list of up to 200 rectangles, and each rectangle's coordinates can go up to 10^9. The constraints guarantee that rectangles have non-zero area and that coordinates are properly ordered (xi1 <= xi2 and yi1 <= yi2).

Edge cases include rectangles that fully overlap, rectangles that touch at edges or corners, and very large rectangles that may cause integer overflow if not handled carefully. The problem essentially requires computing the union area of multiple rectangles, which is a classic computational geometry problem.

Approaches

Brute-Force Approach

A brute-force solution would be to iterate over each unit square in the 2D plane covered by the rectangles, marking cells as covered and then counting them. While this approach is conceptually correct, it is infeasible because the coordinates can be as large as 10^9, making a grid representation impossible. Even optimized versions using sets or maps to store covered points are too slow due to the high potential number of points.

Optimal Approach

The optimal approach uses a sweep line algorithm with a segment tree or coordinate compression with line sweeping. The key idea is:

  1. Sweep a vertical line from left to right across all rectangles.
  2. Track the active intervals (y-ranges of rectangles that intersect the current vertical line) and compute the total vertical coverage.
  3. Multiply the vertical coverage by the horizontal distance moved since the last event to compute the area added.
  4. Use a segment tree or sorted list to efficiently manage adding and removing intervals as the sweep line passes rectangle edges.

This reduces the problem from an infeasible 2D grid to a manageable series of 1D interval calculations along the y-axis, processed at discrete x-coordinates.

Approach Time Complexity Space Complexity Notes
Brute Force O(X*Y) O(X*Y) Not feasible due to large coordinates
Sweep Line + Segment Tree O(N log N) O(N) Efficiently handles overlaps and large coordinates

Algorithm Walkthrough

  1. Extract events: For each rectangle [x1, y1, x2, y2], create two events: (x1, y1, y2, 1) for rectangle start and (x2, y1, y2, -1) for rectangle end. The 1 or -1 indicates whether the interval is being added or removed.

  2. Sort events: Sort all events by x-coordinate. This ensures we process the sweep line in left-to-right order.

  3. Coordinate compression for y-values: Collect all unique y-values from rectangles and map them to a compressed index. This allows us to efficiently maintain intervals in a segment tree or array.

  4. Initialize segment tree or count array: Create a structure to maintain how many times each y-interval is covered.

  5. Sweep line process:

  6. For each x-coordinate event, compute the total vertical coverage based on active intervals.

  7. Multiply the coverage by the difference in x since the previous event to get the area contribution.

  8. Update the active intervals by adding or removing the y-interval from the current rectangle.

  9. Sum area contributions: Keep a running total of the area modulo 10^9 + 7.

Why it works: By processing events in sorted x-order and maintaining active y-intervals, the algorithm ensures that each portion of the plane is counted exactly once, even in regions with multiple overlaps.

Python Solution

from typing import List
from bisect import bisect_left

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        MOD = 10**9 + 7
        events = []
        y_coords = set()

        # Collect events and y-coordinates
        for x1, y1, x2, y2 in rectangles:
            events.append((x1, y1, y2, 1))
            events.append((x2, y1, y2, -1))
            y_coords.add(y1)
            y_coords.add(y2)
        
        # Coordinate compression
        ys = sorted(y_coords)
        y_i = {v: i for i, v in enumerate(ys)}

        count = [0] * (len(ys) - 1)
        events.sort()
        prev_x = 0
        area = 0

        def calc_covered_length():
            length = 0
            for i, c in enumerate(count):
                if c > 0:
                    length += ys[i + 1] - ys[i]
            return length

        for x, y1, y2, typ in events:
            covered_length = calc_covered_length()
            area += covered_length * (x - prev_x)
            area %= MOD
            # Update counts
            for i in range(y_i[y1], y_i[y2]):
                count[i] += typ
            prev_x = x
        
        return area % MOD

Explanation: The code first collects rectangle edges as events and compresses y-coordinates to reduce memory usage. The count array tracks active intervals. At each event, it computes the covered vertical length and multiplies it by the horizontal distance since the last event, adding it to the total area. Intervals are updated according to the rectangle starting or ending.

Go Solution

import (
    "sort"
)

func rectangleArea(rectangles [][]int) int {
    MOD := int(1e9 + 7)
    type Event struct {
        x, y1, y2, typ int
    }

    events := []Event{}
    ySet := map[int]struct{}{}
    for _, r := range rectangles {
        events = append(events, Event{r[0], r[1], r[3], 1})
        events = append(events, Event{r[2], r[1], r[3], -1})
        ySet[r[1]] = struct{}{}
        ySet[r[3]] = struct{}{}
    }

    ys := []int{}
    for y := range ySet {
        ys = append(ys, y)
    }
    sort.Ints(ys)
    yIndex := map[int]int{}
    for i, y := range ys {
        yIndex[y] = i
    }

    count := make([]int, len(ys)-1)
    sort.Slice(events, func(i, j int) bool {
        return events[i].x < events[j].x
    })

    prevX := 0
    area := 0

    calcCovered := func() int {
        length := 0
        for i, c := range count {
            if c > 0 {
                length += ys[i+1] - ys[i]
            }
        }
        return length
    }

    for _, e := range events {
        covered := calcCovered()
        area += covered * (e.x - prevX)
        area %= MOD
        for i := yIndex[e.y1]; i < yIndex[e.y2]; i++ {
            count[i] += e.typ
        }
        prevX = e.x
    }

    return area % MOD
}

Go notes: We use slices and maps for compressed y-coordinates. Sorting is explicit using sort.Slice. Arithmetic modulo 10^9 + 7 is applied during accumulation to prevent overflow.

Worked Examples

Example 1

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]

Step through events:

Event x Active intervals (y) Covered length dx Area contribution
0 [0,2] 2 0 0
1 [0,2],[0,3] 3 1 3
2 [0,3],[0,1] removed 3 1 3
3 none 0 1 0

Total area = 6

Example 2

Input: [[0,0,1000000000,1000000000]]

Only one rectangle:

Event x Active intervals Covered length dx Area contribution
0 [0,1e9] 1e9 0 0
1e9 removed 1e9 1e9 1e18 % MOD = 49

Total area = 49

Complexity Analysis

Measure Complexity Explanation
Time O(N log N + N log N) = O(N log N) Sorting events and computing coverage at each event
Space O(N) Storing events and compressed y-coordinates

Sorting dominates the time complexity.