497. Random Point in Non-overlapping Rectangles LeetCode Solution

In this guide, you will get 497. Random Point in Non-overlapping Rectangles LeetCode Solution with the best time and space complexity. The solution to Random Point in Non-overlapping Rectangles problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Random Point in Non-overlapping Rectangles solution in C++
4. Random Point in Non-overlapping Rectangles solution in Java
5. Random Point in Non-overlapping Rectangles solution in Python
6. Additional Resources

Problem Statement of Random Point in Non-overlapping Rectangles

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 <= 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.

Complexity Analysis

• Time Complexity: O(\log n)
• Space Complexity: O(n)

497. Random Point in Non-overlapping Rectangles LeetCode Solution in C++

class Solution {
 public:
  Solution(vector<vector<int>>& rects) : rects(std::move(rects)) {
    for (const vector<int>& r : this->rects)
      areas.push_back(getArea(r));
    partial_sum(areas.begin(), areas.end(), areas.begin());
  }

  vector<int> pick() {
    const int target = rand() % areas.back();
    const int index = ranges::upper_bound(areas, target) - areas.begin();
    const vector<int>& r = rects[index];
    return {rand() % (r[2] - r[0] + 1) + r[0],
            rand() % (r[3] - r[1] + 1) + r[1]};
  }

 private:
  const vector<vector<int>> rects;
  vector<int> areas;

  int getArea(const vector<int>& r) {
    return (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
  }
};
/* code provided by PROGIEZ */

497. Random Point in Non-overlapping Rectangles LeetCode Solution in Java

class Solution {
  public Solution(int[][] rects) {
    this.rects = rects;
    areas = new int[rects.length];
    for (int i = 0; i < rects.length; ++i)
      areas[i] = getArea(rects[i]) + (i > 0 ? areas[i - 1] : 0);
  }

  public int[] pick() {
    final int target = rand.nextInt(areas[areas.length - 1]);
    final int index = firstGreater(areas, target);
    final int[] r = rects[index];
    return new int[] {
        rand.nextInt(r[2] - r[0] + 1) + r[0],
        rand.nextInt(r[3] - r[1] + 1) + r[1],
    };
  }

  private int[][] rects;
  private int[] areas;
  private Random rand = new Random();

  private int getArea(int[] r) {
    return (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
  }

  private int firstGreater(int[] arr, int target) {
    final int i = Arrays.binarySearch(arr, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}
// code provided by PROGIEZ

497. Random Point in Non-overlapping Rectangles LeetCode Solution in Python

class Solution:
  def __init__(self, rects: list[list[int]]):
    self.rects = rects
    self.areas = list(itertools.accumulate(
        [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]))

  def pick(self) -> list[int]:
    index = bisect_right(self.areas, random.randint(0, self.areas[-1] - 1))
    x1, y1, x2, y2 = self.rects[index]
    return [random.randint(x1, x2), random.randint(y1, y2)]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.