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

# Random Point in Non-overlapping Rectangles

> Tested Python solution for LeetCode 497 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 497, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Math](/catalog/topics/math), [Binary Search](/catalog/topics/binary-search), Reservoir Sampling, [Prefix Sum](/catalog/topics/prefix-sum), Randomized. [View on LeetCode](https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/description/).

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

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

## Problem

You are given an array of non-overlapping axis-aligned rectangles `rects` where `rects[i] = [ai, bi, xi, yi]` indicates that `(ai, bi)` is the bottom-left corner point of the `ith` rectangle and `(xi, yi)` is the top-right corner point of the `ith` rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.

Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.

Note that an integer point is a point that has integer coordinates.

Implement the `Solution` class:

* `Solution(int[][] rects)` Initializes the object with the given rectangles `rects`.
* `int[] pick()` Returns a random integer point `[u, v]` inside the space covered by one of the given rectangles.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/07/24/lc-pickrandomrec.jpg)

```
Input
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
Output
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

Explanation
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // return [1, -2]
solution.pick(); // return [1, -1]
solution.pick(); // return [-1, -2]
solution.pick(); // return [-2, -2]
solution.pick(); // return [0, 0]
```

### Constraints

* `1 <= rects.length <= 100`
* `rects[i].length == 4`
* `-10^9 <= ai < xi <= 10^9`
* `-10^9 <= bi < yi <= 10^9`
* `xi - ai <= 2000`
* `yi - bi <= 2000`
* All the rectangles do not overlap.
* At most `10^4` calls will be made to `pick`.

**Follow up:** What is the time and space complexity of your solution? Could you do it with `O(log n)` pick time using binary search?

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import random
from bisect import bisect_right


class Solution:
    # Weight the rectangles by their integer-point counts with a prefix sum,
    # draw a uniform offset into the total, bisect to the owning rectangle and
    # map the leftover offset onto a (col, row) inside it. Every integer point
    # (perimeter included) gets exactly one offset, so points are uniform.
    # Time: __init__ O(n), pick O(log n)
    # Space: O(n)
    def __init__(self, rects: list[list[int]]) -> None:
        self._rects = rects
        self._prefix: list[int] = []
        total = 0
        for a, b, x, y in rects:
            total += (x - a + 1) * (y - b + 1)
            self._prefix.append(total)
        self._total = total

    def pick(self) -> list[int]:
        target = random.randrange(self._total)
        idx = bisect_right(self._prefix, target)
        base = self._prefix[idx - 1] if idx else 0
        a, b, x, _ = self._rects[idx]
        width = x - a + 1
        offset = target - base
        return [a + offset % width, b + offset // width]
```

## Complexity

| Time | Space |
| - | - |
| **init** O(n), pick O(log n) | O(n) |

## Tags


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