Random Pick With Weight - Leetcode Solution

The problem Random Pick with Weight asks us to design a data structure that allows us to pick an element randomly with probability proportional to its weight.

The input to the data structure is an array of positive integers w, where w[i] represents the weight of ith element. The data structure should support the following function:

int pickIndex() - Returns the index of the element randomly with probability proportional to its weight.

The solution to this problem involves constructing a prefix sum array of the weights, and then using binary search to find the index that satisfies the condition for the probability distribution.

Let s be the prefix sum array of the weight array w. The ith element si of the prefix array represents the sum of all the weights from index 0 to i.

Then, to pick an element randomly with probability proportional to its weight, we generate a random number r between 1 and the sum of all the weights (inclusive). We then use binary search to find the index i such that si-1 < r ≤ si.

The reason for this is that the probability of selecting index i is proportional to the weight wi, which is equal to the difference si-si-1.

Here's the implementation of the pickIndex() function in Python:

class Solution: def init(self, w: List[int]): self.prefix_sum = [0] * len(w) self.prefix_sum[0] = w[0] for i in range(1, len(w)): self.prefix_sum[i] = self.prefix_sum[i-1] + w[i]

def pickIndex(self) -> int:
    rand_num = random.randint(1, self.prefix_sum[-1])
    left, right = 0, len(self.prefix_sum) - 1
    while left < right:
        mid = left + (right - left) // 2
        if rand_num > self.prefix_sum[mid]:
            left = mid + 1
        else:
            right = mid
    return left

The time complexity of constructing the prefix sum array is O(n), and the time complexity of the pickIndex() function is O(log n) due to binary search. The space complexity of the data structure is O(n) to store the prefix sum array.

1