In this Leetcode Random Point in Non-overlapping Rectangles problem solution 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.

## Problem solution in Python.

```class Solution:

def __init__(self, rects: List[List[int]]):
self.ranges = ranges = 
self.rects = rects
for x1,y1,x2,y2 in rects:
ranges.append( ranges[-1] + (y2-y1+1)*(x2-x1+1) )
def pick(self) -> List[int]:
ranges, rects = self.ranges, self.rects
areaPt = random.randint(1,ranges[-1])
x1,y1,x2,y2 = rects[bisect.bisect_left(ranges,areaPt)-1]
return [random.randint(x1,x2), random.randint(y1,y2)]```

## Problem solution in Java.

```class Solution {
TreeMap<Integer, Integer> map;
int size;
int[][] rects;
public Solution(int[][] rects) {
map = new TreeMap<>();
this.rects = rects;
//rects[i] = [x1,y1,x2,y2]
for(int i=0; i<rects.length; i++) {
int[] rect = rects[i];
map.put(size, i);
size += (rect - rect + 1) * (rect - rect + 1);
}
}

public int[] pick() {
int ran = new Random().nextInt(size);
int floorKey = map.floorKey(ran);
int nth = ran - floorKey;
return getCoordinate(rects[map.get(floorKey)], nth);
}

private int[] getCoordinate (int[] rect, int nth) {
int x_length = rect - rect + 1;
int y = nth / x_length;
int x = nth % x_length;
return new int[] {rect + x, rect + y};
}
}```

## Problem solution in C++.

```class Solution {
public:
vector<int> np;
vector<vector<int>> Rects;
Solution(vector<vector<int>>& rects) {
Rects = rects;
for(auto rect : rects){
int l1 = rect - rect + 1;
int l2 = rect - rect + 1;
int val = np.size() ? np.back() + (l1*l2) : l1*l2;
np.push_back(val);
}
}

vector<int> pick() {
int m = np.back();
int r = rand() % m;
auto it = upper_bound(np.begin(), np.end(), r);
int rect = it - np.begin();  //end of step 1
//step 2 begins
vector<int> R = Rects[rect];
int x = rand() % (R-R+1) + R;
int y = rand() % (R-R+1) + R;
return {x, y};
}
};```