# LeetCode 497: Random Point in Non-overlapping Rectangles

## Problem Restatement

We are given a list of non-overlapping axis-aligned rectangles.

Each rectangle is represented as:

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

where:

| Value | Meaning |
|---|---|
| `x1, y1` | Bottom-left corner |
| `x2, y2` | Top-right corner |

All coordinates are integers.

We need to implement a class that can randomly return an integer point inside the area covered by the rectangles.

A point on the border is included.

Every valid integer point across all rectangles must have equal probability of being returned. The official statement specifies that `pick()` returns a random integer point `[u, v]` inside the covered space.

## Input and Output

| Item | Meaning |
|---|---|
| Constructor input | List of rectangles `rects` |
| Method output | One random integer point `[x, y]` |
| Rectangle format | `[x1, y1, x2, y2]` |
| Border rule | Border points are included |
| Distribution rule | Every integer point has equal probability |

Class shape:

```python
class Solution:

    def __init__(self, rects: list[list[int]]):
        ...

    def pick(self) -> list[int]:
        ...
```

## Examples

Example:

```python
rects = [[-2, -2, 1, 1], [2, 2, 4, 6]]
```

The first rectangle contains integer points from `x = -2` to `1` and `y = -2` to `1`.

Its point count is:

```text
(1 - (-2) + 1) * (1 - (-2) + 1)
= 4 * 4
= 16
```

The second rectangle contains integer points from `x = 2` to `4` and `y = 2` to `6`.

Its point count is:

```text
(4 - 2 + 1) * (6 - 2 + 1)
= 3 * 5
= 15
```

So there are:

```text
16 + 15 = 31
```

valid integer points.

Each call to `pick()` should return one of those `31` points with probability `1 / 31`.

## First Thought: Store Every Point

A direct method is to enumerate every integer point in every rectangle and store them in a list.

Then `pick()` can choose a random index from that list.

```python
import random

class Solution:

    def __init__(self, rects: list[list[int]]):
        self.points = []

        for x1, y1, x2, y2 in rects:
            for x in range(x1, x2 + 1):
                for y in range(y1, y2 + 1):
                    self.points.append([x, y])

    def pick(self) -> list[int]:
        return random.choice(self.points)
```

This is uniform, but it may use too much memory.

## Problem With Storing Points

A rectangle may contain many integer points.

For rectangle:

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

the number of integer points is:

```text
(x2 - x1 + 1) * (y2 - y1 + 1)
```

The `+1` matters because the boundary is included.

For example, the interval from `1` to `3` contains:

```text
1, 2, 3
```

which is `3` values, not `2`.

Instead of storing every point, we should store only how many points each rectangle contains.

## Key Insight

Pick one integer from `1` to the total number of valid points.

Then map that integer to a rectangle.

This is weighted random selection.

Each rectangle receives weight equal to its number of integer points.

For example:

| Rectangle | Point count | Global index range |
|---|---:|---|
| `rects[0]` | 16 | `1..16` |
| `rects[1]` | 15 | `17..31` |

If the random number is `20`, it belongs to `rects[1]`.

After choosing the rectangle, choose `x` and `y` uniformly inside that rectangle.

This gives each integer point the same probability because rectangles are chosen proportional to their point counts.

## Prefix Sums

Build a prefix sum array:

```python
prefix[i] = total number of points in rects[0..i]
```

For the example:

```python
point counts = [16, 15]
prefix = [16, 31]
```

To pick:

1. Generate a random integer `t` in `[1, prefix[-1]]`.
2. Use binary search to find the first index `i` where `prefix[i] >= t`.
3. Pick a random integer point inside `rects[i]`.

## Algorithm

In the constructor:

1. Store `rects`.
2. For each rectangle, compute its integer point count:

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

3. Build cumulative prefix sums.

In `pick()`:

1. Choose random integer `t` from `1` to `total`.
2. Binary search `prefix` to find the chosen rectangle.
3. Pick:

```python
x = random.randint(x1, x2)
y = random.randint(y1, y2)
```

4. Return `[x, y]`.

## Correctness

Each rectangle `i` has exactly:

```text
(x2 - x1 + 1) * (y2 - y1 + 1)
```

integer points.

The prefix sum array assigns each rectangle a disjoint range of integer tickets whose length equals its point count.

Choosing `t` uniformly from `1` to the total number of points makes every ticket equally likely.

A rectangle with `c` points receives exactly `c` tickets, so it is selected with probability:

```text
c / total
```

After selecting that rectangle, the algorithm chooses `x` uniformly among its valid x-coordinates and `y` uniformly among its valid y-coordinates. This chooses each integer point inside that rectangle with probability:

```text
1 / c
```

Therefore, any point in that rectangle has total probability:

```text
(c / total) * (1 / c) = 1 / total
```

This is the same for every valid integer point across all rectangles.

Thus `pick()` returns a uniformly random valid point.

## Complexity

Let `n` be the number of rectangles.

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(n)` | `O(n)` |
| `pick()` | `O(log n)` | `O(1)` |

The binary search over prefix sums costs `O(log n)`.

## Implementation

```python
import bisect
import random

class Solution:

    def __init__(self, rects: list[list[int]]):
        self.rects = rects
        self.prefix = []

        total = 0

        for x1, y1, x2, y2 in rects:
            count = (x2 - x1 + 1) * (y2 - y1 + 1)
            total += count
            self.prefix.append(total)

    def pick(self) -> list[int]:
        t = random.randint(1, self.prefix[-1])
        i = bisect.bisect_left(self.prefix, t)

        x1, y1, x2, y2 = self.rects[i]

        x = random.randint(x1, x2)
        y = random.randint(y1, y2)

        return [x, y]
```

## Code Explanation

The constructor stores the rectangles:

```python
self.rects = rects
```

The prefix array stores cumulative point counts:

```python
self.prefix = []
```

For each rectangle, count integer points:

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

The `+1` includes both endpoints.

Then update the running total:

```python
total += count
self.prefix.append(total)
```

In `pick()`, choose one global point ticket:

```python
t = random.randint(1, self.prefix[-1])
```

Find which rectangle owns that ticket:

```python
i = bisect.bisect_left(self.prefix, t)
```

Then choose a point uniformly inside that rectangle:

```python
x = random.randint(x1, x2)
y = random.randint(y1, y2)
```

## Testing

Randomized problems should be tested by checking properties, not exact outputs.

```python
def run_tests():
    rects = [[-2, -2, 1, 1], [2, 2, 4, 6]]
    s = Solution(rects)

    for _ in range(10000):
        x, y = s.pick()

        inside_first = -2 <= x <= 1 and -2 <= y <= 1
        inside_second = 2 <= x <= 4 and 2 <= y <= 6

        assert inside_first or inside_second

    single = Solution([[1, 1, 1, 1]])

    for _ in range(100):
        assert single.pick() == [1, 1]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Two rectangles | Every sampled point must lie in one rectangle |
| Negative coordinates | Checks coordinate ranges below zero |
| Single-point rectangle | Only one possible output |
| Repeated calls | Checks that `pick()` remains valid over many samples |