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. Topics: Array, Math, Binary Search, Reservoir Sampling, Prefix Sum, Randomized. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

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

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, full suite in test_solution.py:

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