Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

497. Random Point in Non-overlapping Rectangles

Time: Constructor: $O(n)$, pick(): $O(\log n)$;

Space: $O(n)$

			


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(begin(areas), end(areas), begin(areas));
  }

  vector<int> pick() {
    const int target = rand() % areas.back();
    const int index =
        upper_bound(begin(areas), end(areas), target) - begin(areas);
    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);
  }
};




			


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[] areas, int target) {
    int l = 0;
    int r = areas.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (areas[m] > target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}




			


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, randint(0, self.areas[-1] - 1))
    x1, y1, x2, y2 = self.rects[index]
    return [randint(x1, x2), randint(y1, y2)]