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 <= 100rects[i].length == 4-109 <= ai < xi <= 109-109 <= bi < yi <= 109xi - ai <= 2000yi - bi <= 2000104 calls will be made to pick.In #497 Random Point in Non-overlapping Rectangles, the goal is to return a random integer point such that every point covered by the given rectangles has an equal probability of being chosen. Since rectangles do not overlap, we can treat the number of integer points inside each rectangle as its weight.
A common strategy is to compute the number of points in each rectangle using (x2 - x1 + 1) * (y2 - y1 + 1) and build a prefix sum array of these counts. When picking a point, generate a random number within the total number of points and use binary search on the prefix sums to determine which rectangle the random index belongs to.
Once the rectangle is selected, generate random coordinates within its boundaries to produce the final point. This approach ensures uniform distribution across all valid points. The preprocessing step builds prefix sums, while each query efficiently selects a rectangle and point using randomized selection and binary search.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Binary Search | Preprocessing: O(n), Pick Operation: O(log n) | O(n) |
| Reservoir Sampling Variant | Pick Operation: O(n) | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums help map a randomly generated point index to the rectangle that contains it. By storing cumulative counts of points across rectangles, we can quickly determine which rectangle corresponds to a given random value.
Yes, this type of problem appears in interviews that test probability, randomized algorithms, and prefix sum techniques. Companies often use similar questions to evaluate understanding of weighted random selection and efficient searching.
An array storing prefix sums is typically the best structure. It allows efficient binary search to locate the rectangle corresponding to a random point index, making the pick operation fast and scalable.
The optimal approach uses prefix sums combined with binary search. Each rectangle contributes a number of integer points, which are accumulated in a prefix sum array. A random index is generated and binary search identifies the rectangle containing that index, ensuring uniform probability.