Rectangle Area II

Rectangle Area II asks for the total area covered by a set of axis-aligned rectangles, where rectangles may overlap. The trap is overlap: you cannot simply add the areas, because shared regions would be counted twice. The clean fix is a sweep line over compressed coordinates.

The slow way first

The brute-force idea is to lay down a grid and mark every covered unit cell, then count the marks. That works only when coordinates are tiny integers, and it is O(area) — hopeless when coordinates reach billions. We need an approach whose cost depends on the number of rectangles, not the size of the plane.

The question to ask: can I slice the plane into vertical strips where the covered shape is simple? If within a strip the set of rectangles never changes, the covered region in that strip is just a width times a covered height.

The idea: compress x, sweep, measure each slab

Take every distinct x edge of every rectangle and sort them. Consecutive x-values define vertical slabs. Inside a single slab, no rectangle starts or ends, so the set of active rectangles (those spanning the whole slab) is fixed. For that slab we merge the y-intervals of the active rectangles to get the covered y-length, then add slab_width * covered_length to a running total.

The key insight: compressing x makes the number of slabs at most 2n - 1, so the whole sweep is independent of how large the coordinates are.

Walk through it

Step through the animation. We have R1 = [0,0,2,2] and R2 = [1,1,3,3]. The distinct xs are 0, 1, 2, 3, giving three slabs. In slab [0,1) only R1 is active (covered length 2). In slab [1,2) both are active, but their y-ranges merge to 0..3 for a covered length of 3 (not 4 — the overlap is removed). In slab [2,3) only R2 is active (covered length 2). Adding 2 + 3 + 2 gives 7.

Pseudocode

xs = sorted set of all x1 and x2 edges
total = 0
for each adjacent pair (x1, x2) in xs:        # one vertical slab
    width = x2 - x1
    active = rectangles whose [r.x1, r.x2] covers [x1, x2]
    merge the y-intervals of active rectangles
    covered = total length of the merged y-intervals
    total += width * covered
return total mod (10**9 + 7)

The Python solution

def rectangle_area(rectangles):
    MOD = 10**9 + 7
    xs = sorted({x for r in rectangles for x in (r[0], r[2])})
    total = 0
    for i in range(len(xs) - 1):
        x1, x2 = xs[i], xs[i + 1]
        width = x2 - x1
        ys = [(r[1], r[3]) for r in rectangles if r[0] <= x1 and x2 <= r[2]]
        covered, prev = 0, -inf
        for lo, hi in sorted(ys):
            covered += max(0, hi - max(lo, prev)); prev = max(prev, hi)
        total += width * covered
    return total % MOD

• Line 3 compresses the x-axis: a sorted set of every rectangle edge. Adjacent pairs are the slabs.
• For each slab [x1, x2), width is its horizontal extent.
• Line 8 collects the y-intervals of the active rectangles — those whose x-span [r[0], r[2]] fully contains the slab.
• Lines 9-11 merge the y-intervals: sort by start, and for each interval add only the part beyond prev, the furthest point covered so far. This removes y-overlap so nothing is double counted.
• We accumulate width * covered per slab and finally take the result modulo 10**9 + 7.

Complexity

With n rectangles there are at most 2n - 1 slabs, and each slab sorts and merges up to n y-intervals, giving O(n^2 log n). A balanced segment tree over compressed y-coordinates can push this to O(n^2) or better, but the slab sweep above is the clearest version to derive in an interview.

When this pattern shows up

Practice