Solution For Random Pick With Weight

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.

Step by Step Implementation For Random Pick With Weight

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */
 
class Solution {
    int sum = 0;
    Random rand = new Random();
    int[] wSums;
    
    public Solution(int[] w) {
        for(int i=0; i wSums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

Solution:

import random

class Solution:

def __init__(self, w: List[int]):

self.w = w

def pickIndex(self) -> int:

# Use the built-in function "random.choices" to

# randomly select an index based on the weight

return random.choices(range(len(self.w)), self.w)[0]

/**
 * @param {number[]} w
 */
var Solution = function(w) {
    
};

/**
 * @param {number} idx
 * @return {number}
 */
Solution.prototype.pickIndex = function() {
    
};

/** 
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(w)
 * var param_1 = obj.pickIndex()
 */

vector w_sum;

class Solution {
public:
    Solution(vector& w) {
        for(int i=1;ipickIndex();
 */

public class Solution {
    private readonly Random _random = new Random();
    private readonly List _prefixSums;
    
    public Solution(int[] w) {
        _prefixSums = new List(w.Length);
        int prefixSum = 0;
        foreach (int weight in w) {
            prefixSum += weight;
            _prefixSums.Add(prefixSum);
        }
    }
    
    public int PickIndex() {
        int target = _random.Next(_prefixSums[_prefixSums.Count - 1]);
        
        // Binary search to find the index corresponding to the target.
        int left = 0, right = _prefixSums.Count - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (_prefixSums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return right;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.PickIndex();
 */