# LeetCode 850: Rectangle Area II

## Problem Restatement

We are given a list of axis-aligned rectangles.

Each rectangle is represented as:

```python
[x1, y1, x2, y2]
```

where:

| Coordinate | Meaning |
|---|---|
| `(x1, y1)` | Bottom-left corner |
| `(x2, y2)` | Top-right corner |

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:

```python
10**9 + 7
```

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | `rectangles`, a list of axis-aligned rectangles |
| Output | Total covered area modulo `10^9 + 7` |
| Rectangle format | `[x1, y1, x2, y2]` |
| Overlap rule | Count overlapping area once |
| Constraint idea | Coordinates can be large, so direct grid marking is impossible |

Function shape:

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

## Examples

Example 1:

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

The total covered area is:

```python
6
```

The overlap is counted once, not once per rectangle.

So the answer is:

```python
6
```

Example 2:

```python
rectangles = [
    [0, 0, 1000000000, 1000000000],
]
```

The area is:

```python
1000000000 * 1000000000
```

Return it modulo `10^9 + 7`.

So the answer is:

```python
49
```

## First Thought: Add Rectangle Areas

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

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

This fails when rectangles overlap.

For example:

```python
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:

```python
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:

```python
area += width * covered_y_length
```

where:

| Value | Meaning |
|---|---|
| `width` | Distance from previous event x to current event x |
| `covered_y_length` | Total union length of active y-intervals |

Each rectangle contributes two events:

| Event | Meaning |
|---|---|
| `(x1, y1, y2, +1)` | Rectangle starts |
| `(x2, y1, y2, -1)` | Rectangle ends |

## 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:

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

The first two overlap, so their union length is:

```python
[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:

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

Events:

```python
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`:

```python
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`:

```python
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`:

```python
width = 1
covered_y_length = 1
area += 1 * 1 = 1
```

Total is:

```python
2 + 3 + 1 = 6
```

Return:

```python
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:

```python
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:

```python
n = len(rectangles)
```

There are `2n` events.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2 log n)` | For each event group, active intervals may be sorted and merged |
| Space | `O(n)` | Active intervals and 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

```python
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:

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

The events are sorted by x-coordinate:

```python
events.sort()
```

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

```python
active = []
```

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

```python
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:

```python
if end <= current_end:
    continue
```

Otherwise, it adds only the uncovered part:

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

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

```python
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

```python
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:

| Test | Why |
|---|---|
| Standard example | Confirms overlapping rectangles are counted once |
| Huge rectangle | Confirms modulo behavior |
| Touching rectangles | Confirms shared edge is not double-counted |
| Partial overlap | Confirms overlap subtraction by union logic |
| Contained rectangle | Confirms inner rectangle adds no extra area |