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:

[x1, y1, x2, y2]

where:

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

Class shape:

class Solution:

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

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

Examples

Example:

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:

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

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

So there are:

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.

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:

[x1, y1, x2, y2]

the number of integer points is:

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

The +1 matters because the boundary is included.

For example, the interval from 1 to 3 contains:

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:

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:

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

For the example:

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:

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:

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

4. Return [x, y].

Correctness

Each rectangle i has exactly:

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

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:

1 / c

Therefore, any point in that rectangle has total probability:

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

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

Implementation

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:

self.rects = rects

The prefix array stores cumulative point counts:

self.prefix = []

For each rectangle, count integer points:

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

The +1 includes both endpoints.

Then update the running total:

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

In pick(), choose one global point ticket:

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

Find which rectangle owns that ticket:

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

Then choose a point uniformly inside that rectangle:

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

Testing

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

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: