How to Solve Random Point in Non-overlapping Rectangles

The key to solving the Random Point in Non-overlapping Rectangles problem is using binary search to efficiently choose a rectangle, followed by picking a random point within that rectangle. This problem tests your ability to implement random sampling with equal probability across multiple non-overlapping areas. With a combination of binary search and prefix sums, the solution efficiently handles multiple queries while ensuring randomness.

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

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.

How GhostInterview Helps

• GhostInterview helps by guiding the candidate through a detailed, step-by-step explanation of binary search and reservoir sampling, ensuring that the candidate can effectively explain and implement both techniques.
• GhostInterview provides real-time feedback and suggestions for optimizing both the solution and the interview approach, emphasizing problem-specific patterns like binary search.
• GhostInterview offers practice with similar problems, helping candidates refine their ability to handle multiple queries efficiently and explain key optimization steps.

Topic Pages

• Array
• Math
• Binary Search
• Reservoir Sampling
• Prefix Sum
• Ordered Set
• Randomized

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.