Watch 10 video solutions for Random Point in Non-overlapping Rectangles, a medium level problem involving Array, Math, Binary Search. This walkthrough by Knowledge Center has 6,362 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given several axis-aligned rectangles that do not overlap. Each call to pick() must return a random integer point from the union of these rectangles, where every valid point across all rectangles has equal probability.
Approach 1: Weighted Rectangle Selection Using Prefix Sum (Initialization: O(n), Pick: O(log n), Space: O(n))
Each rectangle contributes a number of integer points equal to (x2 - x1 + 1) * (y2 - y1 + 1). Treat rectangles as weighted buckets where the weight equals the number of points inside it. Build a prefix sum array of these areas during initialization. When pick() runs, generate a random integer in the range [1, totalPoints] and locate the rectangle containing that index using binary search. After selecting the rectangle, generate two random coordinates inside its bounds to produce the final point. This guarantees uniform probability across all integer points while keeping each pick efficient.
Approach 2: Uniform Randomized Area Selection (Initialization: O(n), Pick: O(n), Space: O(n))
This approach also computes the number of integer points inside each rectangle and stores cumulative areas. Instead of binary searching, you iterate through rectangles subtracting their area until the random index falls within a rectangle’s range. Once the rectangle is identified, generate random x and y coordinates within its bounds. The logic is simple and easy to implement, but rectangle lookup becomes linear. The technique still relies on uniform randomized sampling over total area.
Recommended for interviews: The prefix sum + binary search approach is the expected solution. It demonstrates understanding of weighted random sampling, array preprocessing, and efficient lookup. A linear scan works but scales poorly when pick() is called many times. Showing the brute logic first and then optimizing with prefix sums signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Weighted Rectangle Selection Using Prefix Sum | Init: O(n), Pick: O(log n) | O(n) | Best general solution when pick() is called frequently |
| Uniform Randomized Area Selection (Linear Scan) | Init: O(n), Pick: O(n) | O(n) | Simpler implementation when number of rectangles is small |