Python O(n) time/space solution w/ explanation
Thought process:\nThis problem asks us to find a way to generate a point inside n rectangles with uniform probability, we have a few options:\nOption 1: a trivi
**Thought process:**\nThis problem asks us to find a way to generate a point inside n rectangles with uniform probability, we have a few options:\nOption 1: a trivial solution is to keep track of all the valid integer points, when `pick()` is called just generate a random index and return the integer point at that index. space is `O(nm)` where n is max x coordinate and m is max y coordinate, not space-efficient!\nOption2: instead of tracking all valid integer points, can we track a way to recreate valid integer points? What minimal information do we need to determine whether a integer point is valid?\n* we need all of the rectangles\' x and y borders at least, so space efficiency is lower bounded at `Omega(N)` where `N` is the number of rectangles.\n\nWith information on the rectangles boundaries, we can now pick a rectangle first. The probability of rectangle `i` getting chosen should be `numPoints(rectangle i)/numPoints(total)`--with the rectangle boundaries we have enough information to determine this! If there is a built-in weighted random number generator in your language, you can just use that, I am using Python3 so I have to write this logic manually. There is a couple implementations for this:\n1. we can use a list with each rectangle index appearing n times to mock weight, but this would use `O(nm)` space like option 1. Not efficient!\n2. we can map each rectangle to a range of ints, when a random number is generated we go through each range to identify the rectangle, this would be O(n) time/space where n is the number of rectangles. If you optimize this using binary search the time would be O(logN).\n\nOnce we pick a rectangle, it should be trivial to generate a random point in that rectangle.\n\n**Generalized algorithm:**\n*On initialization:*\n  - build a list of integer point index range for each rectangle, (for example, a rectangle containing 4 valid points would occupy the range(x, x+4)). This is for picking the triangle\n \n*On `pick()`:*\n  * pick the rectangle using weighted random number, using the range map built during initialization\n  * pick a point from the rectangle by randomly generating x and y within rectangle boundaries\n\n**Code:**\n```\nfrom random import randint\nclass Solution:\n    def __init__(self, rects: List[List[int]]):\n        self.rect_rngs = []\n        range_start = 0\n        for x1,y1,x2,y2 in rects:\n            num_points_in_rect = (x2-x1+1) * (y2-y1+1)\n            self.rect_rngs.append([[range_start,range_start+num_points_in_rect], [x1,y1,x2,y2]])\n            range_start = range_start+num_points_in_rect\n        self.total_points = range_start\n    def pick(self) -> List[int]:\n        def pick_rectangle():\n            rnd_int = randint(0,self.total_points-1)\n            for rng, rect in self.rect_rngs:\n                if rng[0]<=rnd_int<rng[1]:\n                    return rect\n            raise ValueError("No matching rectangle found!")\n        x1,y1,x2,y2 = pick_rectangle()\n        pick_x = randint(x1,x2) # randint(a,b) is inclusive!\n        pick_y = randint(y1,y2)\n        return [pick_x, pick_y]\n```\n\nBinary search implementation of `pick`:\n```\n    def pick(self) -> List[int]:\n        def pick_rectangle_binary(l,r, target):\n            if l > r:\n                raise ValueError("No matching rectangle found!")\n            middle = l + (r-l)//2            \n            start = self.rect_rngs[middle][0][0]\n            end = self.rect_rngs[middle][0][1]\n            if start <= target < end:\n                return self.rect_rngs[middle][1]\n            if target < start:\n                return pick_rectangle_binary(l,middle-1,target)\n            else:\n                return pick_rectangle_binary(middle+1,r,target)\n        x1,y1,x2,y2 = pick_rectangle_binary(0,len(self.rect_rngs)-1,randint(0,self.total_points-1))\n        pick_x = randint(x1,x2) # randint(a,b) is inclusive!\n        pick_y = randint(y1,y2)\n        return [pick_x, pick_y]\n```\n\n**Space/time efficiency:**\n`initialization`: Linear time/linear space\n`pick`: Logarithmic time/constant extra space
[]