[Python] Short solution with binary search, explained
Basically, this problem is extention of problem 528. Random Pick with Weight, let me explain why. Here we have several rectangles and we need to choose point fr
Basically, this problem is extention of problem **528. Random Pick with Weight**, let me explain why. Here we have several rectangles and we need to choose point from these rectangles. We can do in in two steps:\n\n1. Choose rectangle. Note, that the bigger number of points in these rectangle the more should be our changes. Imagine, we have two rectangles with 10 and 6 points. Then we need to choose first rectangle with probability `10/16` and second with probability `6/16`.\n2. Choose point inside this rectangle. We need to choose coordinate `x` and coordinate `y` uniformly.\n\nWhen we `initailze` we count weights as `(x2-x1+1)*(y2-y1+1)` because we also need to use boundary. Then we evaluate cumulative sums and normalize.\n\nFor `pick` function, we use **binary search** to find the right place, using uniform distribution from `[0,1]` and then we use uniform discrete distribution to choose coordinates `x` and `y`. \n\n**Complexity**: Time and space complexity of `__init__` is `O(n)`, where `n` is number of rectangles. Time complexity of `pick` is `O(log n)`, because we use binary search. Space complexity of `pick` is `O(1)`.\n\n**Remark**: Note, that there is solution with `O(1)` time/space complexity for `pick`, using smart mathematical trick, see my solution of problem **528**: https://leetcode.com/problems/random-pick-with-weight/discuss/671439/Python-Smart-O(1)-solution-with-detailed-explanation\n\n\n```\nclass Solution:\n    def __init__(self, rects):\n        w = [(x2-x1+1)*(y2-y1+1) for x1,y1,x2,y2 in rects]\n        self.weights = [i/sum(w) for i in accumulate(w)]\n        self.rects = rects\n\n    def pick(self):\n        n_rect = bisect.bisect(self.weights, random.random())\n        x1, y1, x2, y2 = self.rects[n_rect] \n        return [random.randint(x1, x2),random.randint(y1, y2)]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Binary Tree']