We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Random Pick with Weight

Difficulty: Medium

Problem Description

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i-th index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

Key Insights

  • The probability of selecting each index is directly proportional to its weight.
  • The sum of the weights can be calculated once and reused for each selection.
  • A prefix sum array can be used to facilitate random selection based on weights.
  • A binary search can efficiently find the corresponding index for a randomly generated value.

Space and Time Complexity

Time Complexity: O(log n) for pickIndex() after O(n) for preprocessing. Space Complexity: O(n) for the prefix sum array.

Solution

To solve this problem, we will utilize a prefix sum array to store cumulative weights. When the pickIndex() function is called, we generate a random number that falls within the range of the total weight. We then use binary search to find the corresponding index in the prefix sum array where this random number would fit, thereby ensuring that the probability of picking each index corresponds to its weight.

Code Solutions

import random

class Solution:
    def __init__(self, w: List[int]):
        self.prefix_sum = []
        total = 0
        for weight in w:
            total += weight
            self.prefix_sum.append(total)

    def pickIndex(self) -> int:
        target = random.randint(1, self.prefix_sum[-1])
        # Binary search
        left, right = 0, len(self.prefix_sum) - 1
        while left < right:
            mid = (left + right) // 2
            if self.prefix_sum[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
← Back to All Questions