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.
This approach involves calculating the area (number of integer points) of each rectangle and using a prefix sum array to randomly select a rectangle based on these areas. After selecting a rectangle, a random point within that rectangle is generated.
In this implementation, we calculate the total number of integer points for each rectangle and build up a prefix sum array. When picking a point, a random index is generated and used to determine which rectangle the point falls into using binary search. A specific point within this rectangle is then selected by calculating its relative coordinates.
Python
C++
Java
JavaScript
Time Complexity: O(log n) for picking a point due to binary search, where n is the number of rectangles.
Space Complexity: O(n) for storing prefix sums, where n is the number of rectangles.
In this approach, a hash map is used to store all possible integer point coordinates in rectangles. A random point is accessed directly by randomly selecting a key from the hash map. However, this solution is not optimal due to time and space requirements.
This Python solution precomputes every possible point across all rectangles into a hash map. When picking, it simply picks one key directly from the hash map, which leads to high memory usage and unwieldy initialization.
Time Complexity: O(1) for picking, assuming map insertion and access time is constant.
Space Complexity: O(m*n), where m and n are the width and height of the largest rectangle.
| Approach | Complexity |
|---|---|
| Weighted Rectangle Selection Using Prefix Sum | Time Complexity: O(log n) for picking a point due to binary search, where n is the number of rectangles. |
| Uniform Randomized Area Selection | Time Complexity: O(1) for picking, assuming map insertion and access time is constant. |
| Default Approach | — |
| 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 |
Random Point in Non-overlapping Rectangles | LeetCode 497 | C++, Python • Knowledge Center • 6,362 views views
Watch 9 more video solutions →Practice Random Point in Non-overlapping Rectangles with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor