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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Random Pick with Weight

Number: 912

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Uber, Microsoft, LinkedIn, Apple, Shopee, Adobe, X, PayPal, TikTok, Snowflake, Netflix, Yelp, Coinbase, Two Sigma, Rubrik

Problem Description

Given an integer array w where w[i] represents the weight of index i, implement a function pickIndex() that returns an index with a probability proportional to its weight. That is, the probability of picking index i is w[i] / sum(w).

Key Insights

  • Build a prefix sum array from the weights.
  • Calculate the total sum of the weights.
  • Generate a random number in the range [1, total sum] and use binary search to find the corresponding index in the prefix sum array.
  • Using binary search ensures efficient selection in O(log n) time for each call of pickIndex().

Space and Time Complexity

Time Complexity: O(n) for constructing the prefix sum array, and O(log n) per pickIndex() call. Space Complexity: O(n) for storing the prefix sum array.

Solution

The solution leverages a prefix sum array where each entry at index i represents the cumulative sum of weights up to i. After computing the total weight, a random integer is generated between 1 and the total sum (inclusive). A binary search is then used to find the first index where the prefix sum is greater than or equal to the random number. This approach ensures that the index is selected with a probability proportional to its weight.

Code Solutions

import random
import bisect

class Solution:
    def __init__(self, w):
        # Build the prefix sum array.
        self.prefix_sums = []
        current_sum = 0
        for weight in w:
            current_sum += weight
            self.prefix_sums.append(current_sum)
        # Store the total sum of weights.
        self.total_sum = current_sum

    def pickIndex(self):
        # Get a random target in the range [1, total_sum]
        target = random.randint(1, self.total_sum)
        # Use bisect_left to find the proper index.
        index = bisect.bisect_left(self.prefix_sums, target)
        return index

# Example usage:
# solution = Solution([1, 3])
# print(solution.pickIndex())
← Back to All Questions