LeetCode 850: Rectangle Area II

Problem Restatement

We are given a list of axis-aligned rectangles.

Each rectangle is represented as:

[x1, y1, x2, y2]

where:

We need to calculate the total area covered by all rectangles.

If rectangles overlap, the overlapping region should be counted only once.

Since the result can be large, return it modulo:

10**9 + 7

The official problem asks for the union area of all given rectangles, with overlapping area counted once.

Input and Output

Function shape:

class Solution:
    def rectangleArea(self, rectangles: list[list[int]]) -> int:
        ...

Examples

Example 1:

rectangles = [
    [0, 0, 2, 2],
    [1, 0, 2, 3],
    [1, 0, 3, 1],
]

The total covered area is:

6

The overlap is counted once, not once per rectangle.

So the answer is:

6

Example 2:

rectangles = [
    [0, 0, 1000000000, 1000000000],
]

The area is:

1000000000 * 1000000000

Return it modulo 10^9 + 7.

So the answer is:

49

First Thought: Add Rectangle Areas

A tempting solution is to sum the area of every rectangle:

area += (x2 - x1) * (y2 - y1)

This fails when rectangles overlap.

For example:

rectangles = [
    [0, 0, 2, 2],
    [1, 1, 3, 3],
]

Each rectangle has area 4, so the naive sum is 8.

But they overlap in a 1 x 1 square.

The true covered area is:

4 + 4 - 1 = 7

We need to compute the area of the union, not the sum of individual areas.

Key Insight

Use a vertical sweep line.

Imagine moving a vertical line from left to right across the plane.

The set of active rectangles changes only at rectangle left and right edges.

Between two consecutive x-coordinates, the active vertical coverage is constant.

So for each x-slab:

area += width * covered_y_length

where:

Each rectangle contributes two events:

Algorithm

1. Create events from all rectangles.
2. Sort events by x-coordinate.
3. Maintain a list of active y-intervals.
4. Before processing events at the current x, compute area from the previous x to the current x.
5. The height for that slab is the merged length of active y-intervals.
6. Add or remove intervals according to the current x events.
7. Return area modulo 10^9 + 7.

For this guide, we use the simple active-interval approach.

It is easy to understand and works well because the number of rectangles is small.

Merging Active Y-Intervals

Given active intervals such as:

[(0, 2), (1, 3), (5, 7)]

The first two overlap, so their union length is:

[0, 3] length 3
[5, 7] length 2
total = 5

To compute this:

1. Sort intervals by start.
2. Keep the farthest covered end so far.
3. Add only the uncovered part of each interval.

Walkthrough

Use:

rectangles = [
    [0, 0, 2, 2],
    [1, 0, 2, 3],
    [1, 0, 3, 1],
]

Events:

x = 0: add [0, 2]
x = 1: add [0, 3]
x = 1: add [0, 1]
x = 2: remove [0, 2]
x = 2: remove [0, 3]
x = 3: remove [0, 1]

At x = 0, there is no previous width yet.

Add [0, 2].

From x = 0 to x = 1:

width = 1
covered_y_length = 2
area += 1 * 2 = 2

At x = 1, add [0, 3] and [0, 1].

From x = 1 to x = 2:

width = 1
covered_y_length = 3
area += 1 * 3 = 3

Total is now 5.

At x = 2, remove [0, 2] and [0, 3].

From x = 2 to x = 3:

width = 1
covered_y_length = 1
area += 1 * 1 = 1

Total is:

2 + 3 + 1 = 6

Return:

6

Correctness

The sweep line divides the plane into vertical slabs between consecutive rectangle edge x-coordinates.

Inside one slab, no rectangle starts or ends. Therefore, the set of active rectangles is constant throughout the slab.

For that slab, the covered area is exactly:

slab_width * union_length_of_active_y_intervals

because every active y-coordinate segment extends across the full slab width.

The algorithm computes this value for each slab before changing the active set at the next event x-coordinate.

The helper function computes the union length of active y-intervals by sorting and merging intervals. It adds each covered portion exactly once, so overlapping vertical intervals are not double-counted.

Every point covered by at least one rectangle lies in exactly one such vertical slab and inside the merged active y-coverage for that slab. Every point counted by the algorithm is covered by at least one active rectangle.

Therefore, the accumulated area is exactly the total union area of all rectangles.

Complexity

Let:

n = len(rectangles)

There are 2n events.

A segment tree with coordinate compression can reduce the sweep maintenance cost, but the interval-merging version is simpler and accepted under the small rectangle count.

Implementation

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

        events = []

        for x1, y1, x2, y2 in rectangles:
            events.append((x1, 1, y1, y2))
            events.append((x2, -1, y1, y2))

        events.sort()

        def covered_height(intervals: list[tuple[int, int]]) -> int:
            if not intervals:
                return 0

            intervals = sorted(intervals)
            total = 0
            current_end = -1

            for start, end in intervals:
                if end <= current_end:
                    continue

                visible_start = max(start, current_end)
                total += end - visible_start
                current_end = end

            return total

        active = []
        area = 0
        prev_x = events[0][0]
        i = 0

        while i < len(events):
            x = events[i][0]
            width = x - prev_x

            if width:
                height = covered_height(active)
                area = (area + width * height) % MOD

            while i < len(events) and events[i][0] == x:
                _, kind, y1, y2 = events[i]

                if kind == 1:
                    active.append((y1, y2))
                else:
                    active.remove((y1, y2))

                i += 1

            prev_x = x

        return area

Code Explanation

We create one start event and one end event for every rectangle:

events.append((x1, 1, y1, y2))
events.append((x2, -1, y1, y2))

The events are sorted by x-coordinate:

events.sort()

The active list stores y-intervals for rectangles currently crossing the sweep line:

active = []

Before applying events at coordinate x, we compute the area of the slab from prev_x to x:

width = x - prev_x
height = covered_height(active)
area = (area + width * height) % MOD

The helper covered_height merges active intervals.

For each interval, if its end is already covered, it adds nothing:

if end <= current_end:
    continue

Otherwise, it adds only the uncovered part:

visible_start = max(start, current_end)
total += end - visible_start
current_end = end

Then we process all events at the same x-coordinate:

while i < len(events) and events[i][0] == x:

Start events add active intervals.

End events remove active intervals.

Finally, return the accumulated area.

Testing

def run_tests():
    s = Solution()

    assert s.rectangleArea([
        [0, 0, 2, 2],
        [1, 0, 2, 3],
        [1, 0, 3, 1],
    ]) == 6

    assert s.rectangleArea([
        [0, 0, 1000000000, 1000000000],
    ]) == 49

    assert s.rectangleArea([
        [0, 0, 1, 1],
        [1, 0, 2, 1],
    ]) == 2

    assert s.rectangleArea([
        [0, 0, 2, 2],
        [1, 1, 3, 3],
    ]) == 7

    assert s.rectangleArea([
        [0, 0, 3, 3],
        [1, 1, 2, 2],
    ]) == 9

    print("all tests passed")

run_tests()

Test meaning: