Random Pick with Weight

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    You are given an array of positive integer weights w. Implement pickIndex(), which returns a random index i with probability w[i] / sum(w). pickIndex will be called many times, so it must be fast after a one-time setup.

    This looks like a probability question, but it is really prefix sums plus binary search, with a boundary that has to be exactly right. In practice it's weighted load balancing, A/B traffic splits and ad selection. Original problem: LeetCode 528.

    Example

    With weights 2, 5 and 3 out of 10, index 1 should come back half the time.
    With weights 2, 5 and 3 out of 10, index 1 should come back half the time.
    Solution([2, 5, 3])
    pickIndex() -> 1      # probability 5/10
    pickIndex() -> 2      # probability 3/10
    pickIndex() -> 1
    pickIndex() -> 0      # probability 2/10
    # any sequence is valid; over many calls the counts approach 20% / 50% / 30%
    Solution([4])
    pickIndex() -> 0      # always

    Constraints (assumed)

    • 1 ≤ n ≤ 10⁴; 1 ≤ w[i] ≤ 10⁵, so the total fits in 32 bits (just under 10⁹).
    • Up to 10⁴ calls to pickIndex.

    What this question tests

    • Turning weights into ranges on a number line (prefix sums).
    • Binary search for the range that contains a random point, with the correct strict or non-strict comparison.
    • Thinking about follow-ups: changing weights, O(1) picks, and how to test randomness.

    Questions to ask first

    1. Are all weights positive? A zero weight should never be picked; a negative one makes no sense. (Here: positive.)
    2. Will the weights change between picks? That changes the data structure. (Here: no; it's a follow-up.)
    3. Can I use the language's random number generator, and is it uniform? (Here: yes.)
    4. How many picks compared with the array size? Decides whether O(log n) per pick is enough.