LeetCode 497: Random Point in Non-overlapping Rectangles
Problem Description
Explanation:
To solve this problem, we can first calculate the total area covered by all the rectangles. Then, we randomly choose a point inside this total area. Next, we iterate through the rectangles to check if the chosen point lies within any specific rectangle. If it does, we return that point; otherwise, we adjust the chosen point based on the area covered by the previous rectangles.
Time Complexity:
- Initialization: O(n) where n is the number of rectangles
- Pick operation: O(log n)
Space Complexity:
O(n) where n is the number of rectangles
Solutions
class Solution {
int[][] rects;
int[] prefixSums;
Random rand;
public Solution(int[][] rects) {
this.rects = rects;
this.prefixSums = new int[rects.length];
int totalArea = 0;
for (int i = 0; i < rects.length; i++) {
int[] rect = rects[i];
totalArea += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
prefixSums[i] = totalArea;
}
rand = new Random();
}
public int[] pick() {
int randPoint = rand.nextInt(prefixSums[prefixSums.length - 1]) + 1;
int idx = Arrays.binarySearch(prefixSums, randPoint);
if (idx < 0) {
idx = -idx - 1;
}
int[] rect = rects[idx];
int width = rect[2] - rect[0] + 1;
int height = rect[3] - rect[1] + 1;
int base = prefixSums[idx] - width * height;
int offset = randPoint - base;
int x = rect[0] + (offset - 1) % width;
int y = rect[1] + (offset - 1) / width;
return new int[]{x, y};
}
}Related LeetCode Problems
Loading editor...