DSA problem
Random Pick with Weight
You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i-th index. You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking index i is w[i] / sum(w).
The trick that turns this into a binary search problem is the prefix-sum construction. Let prefix[i] = w[0] + w[1] + ... + w[i]. The interval (prefix[i - 1], prefix[i]] (with prefix[-1] = 0) has length exactly w[i]. If you pick a uniformly random integer r from [1, total] where total = prefix[n - 1], the probability that r falls into the i-th interval is exactly w[i] / total.
So pickIndex reduces to: generate r, then binary search for the smallest index i with prefix[i] >= r. That is the lower_bound template applied to the strictly increasing prefix array. The construction runs in O(n) once, in the constructor; every call to pickIndex runs in O(log n) and uses O(1) extra space.
This pattern — convert a discrete distribution to a CDF, draw a uniform sample, binary search the CDF — is the foundation of weighted sampling everywhere, from ad serving to evolutionary algorithms.
Examples
["Solution","pickIndex"], [[[1]],[]][null,0]["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"], [[[1,3]],[],[],[],[],[]][null,1,1,1,1,0]w = [1, 2, 3, 4]index 0: 10%, index 1: 20%, index 2: 30%, index 3: 40%Constraints
- 1 <= w.length <= 10^4
- 1 <= w[i] <= 10^5
- pickIndex will be called at most 10^4 times.
- It is guaranteed that sum(w) does not overflow a 32-bit integer (sum <= 10^9).
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.