{x}
blog image

Random Point in Non-overlapping Rectangles

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.

 

Example 1:

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
  • -109 <= ai < xi <= 109
  • -109 <= bi < yi <= 109
  • xi - ai <= 2000
  • yi - bi <= 2000
  • All the rectangles do not overlap.
  • At most 104 calls will be made to pick.

Solution Explanation

This problem requires generating random points within a set of non-overlapping rectangles. The solution uses a technique combining prefix sums and binary search for efficient random point selection.

Approach:

  1. Calculate Prefix Sums: The core idea is to represent the total area of all rectangles up to a certain index as a prefix sum. We iterate through the rectangles, calculating the area of each rectangle and adding it to the running sum. This sum is stored in the s array. s[i] represents the total area of rectangles from index 0 to i-1.

  2. Random Area Selection: To pick a random point, we first generate a random integer v between 1 and the total area of all rectangles (s[-1] or s[n] in the code). This v represents a random position within the total area.

  3. Binary Search for Rectangle: We use binary search on the s array to efficiently find the index idx of the rectangle containing the point represented by v. The binary search finds the smallest index idx such that s[idx] >= v. This means the randomly selected area falls within the cumulative area up to rectangle idx.

  4. Random Point within Rectangle: Once the rectangle is identified (rects[idx-1] or rects[left-1] in the code), we generate two random integers, one for the x-coordinate and one for the y-coordinate, within the bounds of that rectangle.

Time Complexity Analysis:

  • __init__ or Constructor: O(N), where N is the number of rectangles. This is because we iterate through the rectangles once to calculate the prefix sums.
  • pick: O(log N). The dominant operation is the binary search on the prefix sum array s, which has a time complexity of O(log N). Generating random coordinates within a rectangle is O(1).

Space Complexity Analysis:

  • O(N) to store the prefix sum array s and potentially the rectangles array.

Code Explanation (Python3):

class Solution:
    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.s = [0] * len(rects) # Initialize prefix sum array
        for i, (x1, y1, x2, y2) in enumerate(rects):
            self.s[i] = self.s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1) #Calculate area and add to prefix sum
 
    def pick(self) -> List[int]:
        v = random.randint(1, self.s[-1]) #Generate random area
        idx = bisect_left(self.s, v) #Binary search to find the rectangle
        x1, y1, x2, y2 = self.rects[idx] #get the selected rectangle's coordinates
        return [random.randint(x1, x2), random.randint(y1, y2)] # generate random coordinates within that rectangle

The other language implementations follow the same logic, with minor syntax differences. The bisect_left function in Python is equivalent to lower_bound in C++ and the binary search implementation in Java and Go. They all achieve the same algorithmic efficiency.