Skip to content

497. Random Point in Non-overlapping Rectangles 👎

  • Time: Constructor: $O(n)$, pick(): $O(\log n)$;
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  Solution(vector<vector<int>>& rects) : rects(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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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[] A, int target) {
    final int i = Arrays.binarySearch(A, target + 1);
    return i < 0 ? -i - 1 : i;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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)]