#497

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Random Point in Non-overlapping Rectangles

Design an algorithm to pick random points within non-overlapping rectangles using binary search and reservoir sampling.

array math binary search reservoir sampling prefix sum

Problem Statement

Given an array of non-overlapping axis-aligned rectangles, where each rectangle is defined by two opposite corners, design an algorithm to randomly select an integer point within the space covered by one of these rectangles. Each rectangle is represented as [ai, bi, xi, yi], where (ai, bi) is the bottom-left corner, and (xi, yi) is the top-right corner. A point on the perimeter of a rectangle is also considered inside the rectangle's space.

Your solution should ensure that any point within the covered area has an equal probability of being chosen. The solution needs to handle multiple queries efficiently, ensuring each point is selected with uniform probability. Constraints ensure there are no overlaps between the rectangles and the total number of pick queries will not exceed 10^4.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 Approach

Binary Search for Rectangle Selection

To pick a random point efficiently, first calculate the area covered by all rectangles using a prefix sum array. Then, for each query, use binary search on the prefix sum array to choose which rectangle to pick from, ensuring each rectangle's area is taken into account with equal probability.

Reservoir Sampling for Point Selection

Once a rectangle is chosen using binary search, randomly select a point within the rectangle using reservoir sampling. This approach guarantees that any point inside the rectangle, including its boundary, is chosen with equal probability.

Efficient Query Handling with Preprocessing

The solution involves preprocessing the area of each rectangle into a prefix sum array, which allows each query to be answered in logarithmic time, ensuring efficiency even with a large number of queries.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for preprocessing is O(n), where n is the number of rectangles. Each query is answered in O(log n) due to binary search over the prefix sum array. The space complexity is O(n) for storing the prefix sum array and rectangle information.

What Interviewers Usually Probe

Can the candidate explain how binary search is applied to pick a rectangle based on area distribution?
Does the candidate understand how to maintain equal probability for point selection within the chosen rectangle?
Can the candidate efficiently handle multiple queries with preprocessing, ensuring that the solution scales?

Common Pitfalls or Variants

Common pitfalls

Failing to account for the non-overlapping condition, which simplifies the problem by ensuring there is no need for complex collision detection.
Misunderstanding how to use binary search to select rectangles based on area rather than simply picking a random rectangle.
Not ensuring that every point within the selected rectangle is equally likely to be chosen, especially with multiple queries.

Follow-up variants

Modifying the problem to handle overlapping rectangles would require additional complexity in the rectangle selection process.
Extending the problem to allow weighted probability for each rectangle would involve adjusting the prefix sum logic to account for different weights.
Introducing dynamic rectangle modifications (e.g., adding or removing rectangles) would require an updated approach for maintaining the prefix sum array.

FAQ

How does binary search help in solving the Random Point in Non-overlapping Rectangles problem?

Binary search is used to efficiently select one rectangle based on the cumulative area of all rectangles, ensuring each rectangle is equally likely to be chosen.

What is the role of reservoir sampling in this problem?

Reservoir sampling is used to randomly select a point inside the chosen rectangle with equal probability, ensuring fairness in point selection.

What is the time complexity of this solution?

The time complexity for preprocessing the rectangles is O(n), and each query is answered in O(log n) time due to binary search over the prefix sum array.

How do you ensure that points on the perimeter are included in the solution?

The solution explicitly considers the perimeter of the rectangle as part of the valid point space, ensuring that points on the boundary are equally likely to be selected.

Can this solution be optimized further for more queries?

The current solution is already efficient with O(log n) query time. Further optimizations would likely focus on the data structure used for maintaining rectangles or handling dynamic updates.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

    def pick(self) -> List[int]:
        v = random.randint(1, self.s[-1])
        idx = bisect_left(self.s, v)
        x1, y1, x2, y2 = self.rects[idx]
        return [random.randint(x1, x2), random.randint(y1, y2)]


# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()

Continue Practicing

#528 random pick with weight #363 max sum of rectangle no larger than k #710 random pick with blacklist