Domain 2MediumCORE

Random Pick with Weight

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 $P(i) = frac{w[i]}{sum(w)}$.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Binary Search#Random

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 P(i)=w[i]∑(w)P(i) = \frac{w[i]}{\sum(w)}.

Inputs:

  • Array w: List of positive integers. Length up to 10,000. Values up to 10510^5.
  • 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 w is fixed but we query many times, the cost of initialization should be amortized over queries. We cannot afford O(N)O(N) per query if total calls are high (104×104=10810^4 \times 10^4 = 10^8 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.randint with 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 O(N)O(N) time per call. With 10,000 calls on an array of size 10,000, this is roughly 10810^8 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

  1. Preprocessing: In the constructor __init__(self, w), compute the cumulative weights array (prefix_w). For example, if w = [10, 50], then prefix_w becomes [10, 60]. The last element represents the total weight.
  2. Random Selection: In pickIndex(), generate a random integer between 1 and total_weight (inclusive). This gives us a target value within our cumulative range.
  3. Binary Search: Use binary search (bisect_left) on the prefix_w array 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 O(log⁡N)O(\log N) per query.

Complexity Analysis

  • Time:
    • Initialization: O(N)O(N) to build the cumulative array.
    • pickIndex: O(1)O(1) for random generation + O(log⁡N)O(\log N) for binary search (bisect_left). Total per call is dominated by log⁡N\log N.
  • Space: O(N)O(N) 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.randint returns that value. bisect_left finds index 0 immediately. Correctly handles probability of 100%.
  • Large Weights/Sum: Python integers handle arbitrary size, so even if the total weight exceeds 231−12^{31}-1, logic remains valid without overflow errors (unlike fixed-width integer languages).
  • Uniform Distribution: If all weights are equal, prefix_w is linear. The random number falls uniformly across indices, resulting in uniform probability distribution as expected.