> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Rectangle Area II Python Solution with Tests

> Tested Python solution for LeetCode 850 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 850, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Segment Tree](/catalog/topics/segment-tree), Sweep Line, [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/rectangle-area-ii/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 850   # by problem number
lcpy gen -s rectangle_area_ii   # by problem name
```

## Problem

You are given a 2D array of axis-aligned rectangles. Each `rectangle[i] = [xi1, yi1, xi2, yi2]` denotes the ith rectangle where `(xi1, yi1)` are the coordinates of the bottom-left corner, and `(xi2, yi2)` are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo `10^9 + 7`.

### Examples

![Example 1](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png)

```
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
```

```
Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is 49.
```

### Constraints

* 1 \<= rectangles.length \<= 200
* rectangles\[i].length == 4
* 0 \<= xi1, yi1, xi2, yi2 \<= 10^9
* xi1 \<= xi2
* yi1 \<= yi2
* All rectangles have non zero area.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/rectangle_area_ii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/rectangle_area_ii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2) cells per sweep with n <= 200 rectangles, so ~10^5 cell updates
    # Space: O(n^2) for the compressed coverage grid
    def rectangle_area(self, rectangles: list[list[int]]) -> int:
        mod = 1_000_000_007
        xs = sorted({r[0] for r in rectangles} | {r[2] for r in rectangles})
        ys = sorted({r[1] for r in rectangles} | {r[3] for r in rectangles})
        x_index = {x: i for i, x in enumerate(xs)}
        y_index = {y: i for i, y in enumerate(ys)}
        covered = [[False] * (len(ys) - 1) for _ in range(len(xs) - 1)]
        for x1, y1, x2, y2 in rectangles:
            for i in range(x_index[x1], x_index[x2]):
                row = covered[i]
                for j in range(y_index[y1], y_index[y2]):
                    row[j] = True
        total = 0
        for i in range(len(xs) - 1):
            width = xs[i + 1] - xs[i]
            row = covered[i]
            for j in range(len(ys) - 1):
                if row[j]:
                    total += width * (ys[j + 1] - ys[j])
        return total % mod
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) cells per sweep with n \<= 200 rectangles, so \~10^5 cell updates | O(n^2) for the compressed coverage grid |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.