528. Random Pick with Weight.md

528. Random Pick with Weight (Medium)

• create prefix sum matrix, randon choose a weight from the range or 0 to max(sum matrix)
• binary search for the range. pick a number based on the range.

class Solution:

    def __init__(self, w: List[int]):
        self.w = w
        self.prefix_sum = []
        sum_val = 0
        for one_w in w:
            sum_val += one_w
            self.prefix_sum.append(sum_val)
        # print(self.prefix_sum)
    def pickIndex(self) -> int:
        max_sum = max(self.prefix_sum)
        randon_weight = random.randint(1, max_sum)
        left, right = 0, len(self.prefix_sum) - 1
        while(left <= right):
            mid = left + (right - left) // 2
            if randon_weight <= self.prefix_sum[mid]:
                temp_ans = mid
                right = mid - 1
            else:
                left = mid + 1 
        return temp_ans