##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/497.html

# 497. Random Point in Non-overlapping Rectangles (Medium)

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

1. An integer point is a point that has integer coordinates.
2. A point on the perimeter of a rectangle is included in the space covered by the rectangles.
3. ith rectangle = rects[i][x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
4. length and width of each rectangle does not exceed 2000.
5. 1 <= rects.length <= 100
6. pick return a point as an array of integer coordinates [p_x, p_y]
7. pick is called at most 10000 times.

Example 1:

Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]


Example 2:

Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Related Topics:
Binary Search, Random

Similar Questions:

// OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
// Time:
//      Solution: O(N)
//      pick: O(logN)
// Space: O(N)
class Solution {
vector<vector<int>> A;
vector<int> size;
int total = 0;
public:
Solution(vector<vector<int>>& rects) : A(rects) {
for (auto &r : A) size.push_back(total += (r - r + 1) * (r - r + 1));
}
vector<int> pick() {
int r = rand() % total;
int i = upper_bound(begin(size), end(size), r) - begin(size);
r -= i > 0 ? size[i - 1] : 0;
int w = A[i] - A[i] + 1;
return { A[i] + r / w, A[i] + r % w };
}
};

• class Solution {
int rectsCount;
int[][] rects;
int[] accumulatedPoints;
int pointsCount;

public Solution(int[][] rects) {
rectsCount = rects.length;
this.rects = rects;
accumulatedPoints = new int[rectsCount];
for (int i = 0; i < rectsCount; i++) {
int[] rect = rects[i];
int points = (rect - rect + 1) * (rect - rect + 1);
accumulatedPoints[i] = points;
pointsCount += points;
}
for (int i = 1; i < rectsCount; i++)
accumulatedPoints[i] += accumulatedPoints[i - 1];
}

public int[] pick() {
int pointsPosition = (int) (Math.random() * pointsCount);
int index = 0;
for (int i = 0; i < rectsCount; i++) {
if (accumulatedPoints[i] > pointsPosition) {
index = i;
break;
}
}
int[] rect = rects[index];
int xMin = rect, xMax = rect;
int yMin = rect, yMax = rect;
int randomX = xMin + (int) (Math.random() * (xMax - xMin + 1));
int randomY = yMin + (int) (Math.random() * (yMax - yMin + 1));
int[] randomPoint = {randomX, randomY};
return randomPoint;
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
############

class Solution {
private int[] s;
private int[][] rects;
private Random random = new Random();

public Solution(int[][] rects) {
int n = rects.length;
s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + (rects[i] - rects[i] + 1) * (rects[i] - rects[i] + 1);
}
this.rects = rects;
}

public int[] pick() {
int n = rects.length;
int v = 1 + random.nextInt(s[n]);
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (s[mid] >= v) {
right = mid;
} else {
left = mid + 1;
}
}
int[] rect = rects[left - 1];
return new int[] {rect + random.nextInt(rect - rect + 1),
rect + random.nextInt(rect - rect + 1)};
}
}

/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/

• // OJ: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
// Time:
//      Solution: O(N)
//      pick: O(logN)
// Space: O(N)
class Solution {
vector<vector<int>> A;
vector<int> size;
int total = 0;
public:
Solution(vector<vector<int>>& rects) : A(rects) {
for (auto &r : A) size.push_back(total += (r - r + 1) * (r - r + 1));
}
vector<int> pick() {
int r = rand() % total;
int i = upper_bound(begin(size), end(size), r) - begin(size);
r -= i > 0 ? size[i - 1] : 0;
int w = A[i] - A[i] + 1;
return { A[i] + r / w, A[i] + r % w };
}
};

• class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.s =  * len(rects)
for i, (x1, y1, x2, y2) in enumerate(rects):
self.s[i] = self.s[i - 1] + (x2 - x1 + 1) * (y2 - y1 + 1)

def pick(self) -> List[int]:
v = random.randint(1, self.s[-1])
idx = bisect_left(self.s, v)
x1, y1, x2, y2 = self.rects[idx]
return [random.randint(x1, x2), random.randint(y1, y2)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()

############

class Solution(object):

def __init__(self, rects):
"""
:type rects: List[List[int]]
"""
self.rects = rects
self.N = len(rects)
areas = [(x2 - x1 + 1) * (y2 - y1 + 1) for x1, y1, x2, y2 in rects]
self.preSum =  * self.N
self.preSum = areas
for i in range(1, self.N):
self.preSum[i] = self.preSum[i - 1] + areas[i]
self.total = self.preSum[-1]

def pickRect(self):
rand = random.randint(0, self.total - 1)
return bisect.bisect_right(self.preSum, rand)

def pickPoint(self, rect):
x1, y1, x2, y2 = rect
x = random.randint(x1, x2)
y = random.randint(y1, y2)
return x, y

def pick(self):
"""
:rtype: List[int]
"""
rectIndex = self.pickRect()
rect = self.rects[rectIndex]
return self.pickPoint(rect)

# Your Solution object will be instantiated and called as such:
# obj = Solution(rects)
# param_1 = obj.pick()

• type Solution struct {
s     []int
rects [][]int
}

func Constructor(rects [][]int) Solution {
n := len(rects)
s := make([]int, n+1)
for i, v := range rects {
s[i+1] = s[i] + (v-v+1)*(v-v+1)
}
return Solution{s, rects}
}

func (this *Solution) Pick() []int {
n := len(this.rects)
v := 1 + rand.Intn(this.s[len(this.s)-1])
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if this.s[mid] >= v {
right = mid
} else {
left = mid + 1
}
}
rect := this.rects[left-1]
x, y := rect+rand.Intn(rect-rect+1), rect+rand.Intn(rect-rect+1)
return []int{x, y}
}