Random Pick with Weight

Medium Binary Search Basics Original on LeetCode

Random Pick with Weight is a medium binary search problem solved with the basics pattern. The best approach, optimal (prefix sums + binary search), runs in constructor O(n), pickIndex O(log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (linear scan over the weights) up.

Problem

You are given an array w of positive integers, where w[i] is the weight of index i. Build a class (named Solution) whose pickIndex() method returns a random index, where index i is chosen with probability w[i] / sum(w).

For example, with w = [1, 3], index 0 should come back about 25% of the time and index 1 about 75% of the time. The constructor Solution(w) receives the weights once; pickIndex() is then called many times.

Examples

Example 1

Input
Solution([5]), pickIndex(), pickIndex()
Output
0, 0
Why
There is only one index, so every pick returns 0.

Example 2

Input
Solution([2, 6]), pickIndex(), pickIndex(), pickIndex()
Output
for example 1, 1, 0
Why
Index 0 is returned with probability 2/8 = 25% and index 1 with probability 6/8 = 75%. Any sequence of valid indices is accepted, as long as the frequencies follow the weights over many calls.

Constraints

  • 1 <= w.length <= 10^4
  • 1 <= w[i] <= 10^5
  • pickIndex is called at most 10^4 times.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (linear scan over the weights)constructor O(n), pickIndex O(n)O(n)
Optimal (prefix sums + binary search)constructor O(n), pickIndex O(log n)O(n)

1Brute force (linear scan over the weights)

Timeconstructor O(n), pickIndex O(n)Each pick may walk through every weight.
SpaceO(n)The stored weights.

Draw a random integer r between 1 and the total weight. Walk the weights from the left, subtracting each one from r; the index where r drops to zero or below is the segment r landed in.

  1. Constructor: store the weights and their total.
  2. pickIndex: r = random integer in [1, total].
  3. For each i, r -= w[i]; if r <= 0, return i.
class Solution {
    private final int[] w;
    private int total = 0;
    private final Random rnd = new Random();

    public Solution(int[] w) {
        this.w = w;
        for (int x : w) total += x;
    }

    public int pickIndex() {
        int r = rnd.nextInt(total) + 1;
        for (int i = 0; i < w.length; i++) {
            r -= w[i];
            if (r <= 0) return i;
        }
        return w.length - 1;
    }
}

Edge cases to test

  • A single weight: always return 0
  • All weights equal: every index is equally likely
  • One weight much larger than the others
  • The random draw lands exactly on a prefix-sum boundary

Hints

Hint 1

Picture the weights laid end to end on a number line of length total. A uniform random point on that line falls inside index i's segment with probability w[i] / total.

Hint 2

Draw a random integer r in [1, total] and find which segment contains it.

Hint 3

Prefix sums are sorted, so the segment is the first prefix sum that is >= r, found with binary search.

FAQ

What is the best time complexity for Random Pick with Weight?

Optimal (prefix sums + binary search) runs in constructor O(n), pickIndex O(log n) time and O(n) extra space. One pass builds the prefix sums; each pick is a single binary search.

Which pattern does Random Pick with Weight use?

It is a binary search problem that uses the basics pattern. Other problems with the same pattern: Fundamentals, Binary Search, Time Based Key-Value Store.

Is there a brute force solution for Random Pick with Weight?

Yes. Brute force (linear scan over the weights) takes constructor O(n), pickIndex O(n) time and O(n) space. Draw a random integer r between 1 and the total weight.

Which edge cases should I test for Random Pick with Weight?

A single weight: always return 0; All weights equal: every index is equally likely; One weight much larger than the others; The random draw lands exactly on a prefix-sum boundary.