LC497 Random Point in Non-overlapping Rectangles

class Solution:

    def __init__(self, rects: List[List[int]]):
        self.rects = rects
        self.weight = []
        s = 0 # area of rectangula 
        for rect in self.rects:
            area = (rect[2] - rect[0] + 1 ) * (rect[3] - rect[1] + 1 ) # to include edge of rectangular
            s += area
            self.weight.append(s)
    def pick(self) -> List[int]:
        idx = bisect.bisect_left(self.weight,random.randint(1,self.weight[-1])) 
        rect = self.rects[idx]
        return [random.randint(rect[0],rect[2]),random.randint(rect[1],rect[3])]
        

class Solution(object):
    def __init__(self, rects):
        self.rects = rects
        self.psum = []
        self.sm = 0
        for x1, y1, x2, y2 in self.rects:
            area = (y2 - y1 + 1) * (x2 - x1 + 1)
            self.sm += area
            self.psum.append(self.sm)
    def pick(self):
        val = random.randint(0, self.sm - 1)
        left, right = 0, len(self.psum)-1
        while left < right: 
            mid = left + (right - left) // 2
            if self.psum[mid] > val:
                right = mid
            else:
                left = mid + 1
        # chosen rectangle index is left
        x1, y1, x2, y2 = self.rects[left]
        height, width = y2 - y1 + 1, x2 - x1 + 1
        base = self.psum[left] - height * width
        x = x1 + (val - base) % width 
        y = y1 + (val - base) // width
        return x, y