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 = [0] 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[2] - rect[0] + 1) * (rect[3] - rect[1] + 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[2] - rect[0] + 1; int y = nth / x_length; int x = nth % x_length; return new int[] {rect[0] + x, rect[1] + 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[2] - rect[0] + 1; int l2 = rect[3] - rect[1] + 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[2]-R[0]+1) + R[0]; int y = rand() % (R[3]-R[1]+1) + R[1]; return {x, y}; } };

## 0 Comments