LeetCode 497: Random Point in Non-overlapping Rectangles Solution
Master LeetCode problem 497 (Random Point in Non-overlapping Rectangles), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
497. Random Point in Non-overlapping Rectangles
Problem Explanation
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
Solution Code
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};
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 497 (Random Point in Non-overlapping Rectangles)?
This page provides optimized solutions for LeetCode problem 497 (Random Point in Non-overlapping Rectangles) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 497 (Random Point in Non-overlapping Rectangles)?
The time complexity for LeetCode 497 (Random Point in Non-overlapping Rectangles) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 497 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 497 in Java, C++, or Python.