528. Random Pick with Weight
Model: qwen3.5:9b
Topics: Binary Search,Random
FAANG asked: 1
Acceptance rate: 44.7%
Problem Breakdown
We are given a list of positive integers w representing weights for each index in an array. We need to implement a method pickIndex() that returns an integer from [0, w.length - 1]. The critical constraint is probabilistic: the probability of returning index i must be exactly proportional to its weight w[i], specifically .
Inputs:
- Array
w: List of positive integers. Length up to 10,000. Values up to . - Method call:
pickIndex()called multiple times (up to 10,000).
Outputs:
- Integer index based on weighted probability distribution.
Implicit Constraints & Edge Cases:
- Initialization vs Query Cost: Since
wis fixed but we query many times, the cost of initialization should be amortized over queries. We cannot afford per query if total calls are high ( operations might TLE in Python). - Overflow: Summing weights could exceed standard integer limits, but Python handles arbitrary precision integers automatically. However, we must ensure the random generation logic covers the full sum space without floating-point errors (using
random.randintwith total weight is safer than float multiplication for exact bucket mapping). - Single Element: If array length is 1, probability is 100% to return index 0. The algorithm should handle this naturally.
Intuition
A naive approach would be: inside pickIndex(), iterate through the weights and accumulate them until we find a cumulative sum that exceeds our randomly generated target value. This allows us to determine which “bucket” (index) corresponds to the random number. However, iterating takes time per call. With 10,000 calls on an array of size 10,000, this is roughly operations, which risks a Time Limit Exceeded in Python or slower languages like Java/C++.
The key insight for optimization is Preprocessing. Since the weights w do not change between queries, we can precompute the cumulative sums (prefix sums) of the array. This transforms our lookup from linear to logarithmic time using binary search. We essentially map a continuous range [1, TotalWeight] into discrete indices based on where that random number falls within the prefix sum boundaries.
Approach
- Preprocessing: In the constructor
__init__(self, w), compute the cumulative weights array (prefix_w). For example, ifw = [10, 50], thenprefix_wbecomes[10, 60]. The last element represents the total weight. - Random Selection: In
pickIndex(), generate a random integer between1andtotal_weight(inclusive). This gives us a target value within our cumulative range. - Binary Search: Use binary search (
bisect_left) on theprefix_warray to find the first index where the prefix sum is greater than or equal to our random number. The returned index from this operation corresponds directly to the original weight index we want to return. This gives us per query.
Complexity Analysis
- Time:
- Initialization: to build the cumulative array.
pickIndex: for random generation + for binary search (bisect_left). Total per call is dominated by .
- Space: to store the prefix sum array.
Solution
import random
from bisect import bisect_left
class Solution:
def __init__(self, w):
"""
Precompute cumulative weights for O(logN) lookup during pickIndex calls.
:type w: List[int]
"""
self.prefix_w = []
current_sum = 0
# Build prefix sum array where each element is the inclusive weight up to that index
for val in w:
current_sum += val
self.prefix_w.append(current_sum)
def pickIndex(self):
"""
Returns an index proportional to its weight.
:rtype: int
"""
# Generate a random number between 1 and the total sum (inclusive).
# This maps directly into our cumulative range [prefix_w[0], prefix_w[-1]].
target = random.randint(1, self.prefix_w[-1])
# Find the first index in prefix_w where value >= target.
# bisect_left returns insertion point to maintain order;
# since we want the bucket that covers 'target', this is exactly what we need.
return bisect_left(self.prefix_w, target)
# Example usage:
# solution = Solution([1, 3])
# print(solution.pickIndex())
Edge Cases Handled
- Single Element Array: The prefix sum array will have one element
[w[0]].random.randintreturns that value.bisect_leftfinds index 0 immediately. Correctly handles probability of 100%. - Large Weights/Sum: Python integers handle arbitrary size, so even if the total weight exceeds , logic remains valid without overflow errors (unlike fixed-width integer languages).
- Uniform Distribution: If all weights are equal,
prefix_wis linear. The random number falls uniformly across indices, resulting in uniform probability distribution as expected.