Python O(n) by pool sampling. [w/ Visualization]
Hint:\n\nThink of pool sampling.\n\nTotal n pools, and total P points\n\n\n\nEach rectangle acts as pool_i with points p_i  by itself,\nwhere p_i = ( x_i_2 - x_
**Hint**:\n\nThink of **pool sampling**.\n\nTotal **n** pools, and total **P** points\n\n![image](https://assets.leetcode.com/users/images/09745dec-53dc-400f-8b83-b710ec195706_1598089506.3815591.png)\n\nEach **rectangle** acts as **pool_i** with points **p_i**  by itself,\nwhere p_i = ( x_i_2 - x_i_1 + 1) * ( y_i_2 - y_i_1 + 1 )\n\n![image](https://assets.leetcode.com/users/images/dffe86ac-b80f-4271-a317-861aaf148f15_1598089224.7017436.png)\n\n\nSo, p_1 + p_2 + ... + p_n = P, and\neach pool_i has a **weight** of **p_i / P** during **pool sampling**.\n\nThen, generate a random number **r** from 1 to P\n\nCompute the **pool index** (i.e., **rectangle index**) from r by bisection\n\nThen compute the **corresponding x, y coordinate** in that pool from r by modulo and division.\n\n---\n\n```\nfrom random import randint\nfrom bisect import bisect_left\n\nclass Solution:\n\n    def __init__(self, rects: List[List[int]]):\n        \n        self.rectangles = rects\n        \n        # record prefix sum of points number (i.e., acts like the CDF)\n        self.prefix_points_sum = []\n        \n        for x1, y1, x2, y2 in rects:\n            \n            # compute current number of points\n            cur_points = ( x2 - x1 + 1 ) * ( y2 - y1 + 1)\n            \n            # update to prefix table\n            if self.prefix_points_sum:\n                self.prefix_points_sum.append( self.prefix_points_sum[-1] + cur_points )\n                \n            else:\n                self.prefix_points_sum.append( cur_points )\n        \n            \n\n    def pick(self) -> List[int]:\n        \n        total_num_of_points = self.prefix_points_sum[-1]\n        \n        # get a random point serial, sampling from 1 ~ total number of points\n        random_point_serial = randint(1, total_num_of_points)\n        \n        # get the rectangle index by looking up prefix table with bisection\n        idx_of_rectangle = bisect_left(self.prefix_points_sum, random_point_serial)\n        \n        # get the point range of that rectangle by index\n        x1, y1, x2, y2 = self.rectangles[idx_of_rectangle]\n        \n        # compute the offset value between prefix sum and random point serial\n        offset = self.prefix_points_sum[idx_of_rectangle] - random_point_serial\n        \n        # compute corresponding x, y points coordination in that rectangle\n        x = offset % ( x2 - x1 + 1) + x1\n        y = offset // ( x2 - x1 + 1) + y1\n        \n        return [x, y]\n```
['Math', 'Python', 'Python3']