Random Point in Non-overlapping Rectangles

Over 50% downvotes

You can create a class to manage the given rectangles and implement a function to pick a random integer point inside one of the rectangles. Here’s Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import random

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.weights = [0]
        for x1, y1, x2, y2 in rects:
            self.weights.append(self.weights[-1] + (x2 - x1 + 1) * (y2 - y1 + 1))

    def pick(self) -> List[int]:
        rand_val = random.randint(0, self.weights[-1] - 1)
        index = self._binary_search(rand_val)
        x1, y1, x2, y2 = self.rects[index]
        return [random.randint(x1, x2), random.randint(y1, y2)]

    def _binary_search(self, val: int) -> int:
        left, right = 0, len(self.weights) - 1
        while left < right:
            mid = (left + right) // 2
            if self.weights[mid] <= val:
                left = mid + 1
            else:
                right = mid
        return left - 1

Explanation:

  • We’re using a binary search to efficiently locate the target rectangle. The _binary_search method locates the rectangle that the random value falls within.
  • In the pick method, we select a random value and find the corresponding rectangle. Then we return a random point within that rectangle’s bounds.
  • The weights are used to ensure that each point in the overall space is equally likely to be chosen. We store the cumulative weights, where the weight of a rectangle is proportional to its area.