Leetcode Problem 497. Random Point in Non-overlapping Rectangles
Leetcode Solutions
Weighted Random Selection of Rectangles
- Calculate the area of each rectangle and store these values.
- Compute a prefix sum array of the areas to use as weights for random selection.
- To pick a random rectangle, generate a random integer between 1 and the sum of all rectangle areas.
- Use binary search to find the rectangle corresponding to the random integer based on the prefix sum array.
- Once the rectangle is chosen, generate a random point within the rectangle's boundaries.
- Return the random point.
Sequential Rectangle Selection and Random Point Generation
Ask Question
Programming Language
Purpose:
image/screenshot of info(optional)
Full Screen
Loading...
Suggested Answer
Answer
Full Screen
Copy Answer Code
Loading...