Random Pick with Weight
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^41 <= w[i] <= 10^5pickIndexis called at most10^4times.
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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
constructor O(n), pickIndex O(n)Each pick may walk through every weight.O(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.
- Constructor: store the weights and their total.
- pickIndex: r = random integer in [1, total].
- 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;
}
}import random
class Solution:
def __init__(self, w: List[int]):
self.w = w
self.total = sum(w)
def pickIndex(self) -> int:
r = random.randint(1, self.total)
for i, x in enumerate(self.w):
r -= x
if r <= 0:
return i
return len(self.w) - 1class Solution {
vector<int> w;
int total = 0;
mt19937 gen{random_device{}()};
public:
Solution(vector<int>& w) : w(w) {
for (int x : w) total += x;
}
int pickIndex() {
int r = uniform_int_distribution<int>(1, total)(gen);
for (int i = 0; i < (int)w.size(); i++) {
r -= w[i];
if (r <= 0) return i;
}
return w.size() - 1;
}
};class Solution {
constructor(w) {
this.w = w;
this.total = w.reduce((a, b) => a + b, 0);
}
pickIndex() {
let r = Math.floor(Math.random() * this.total) + 1;
for (let i = 0; i < this.w.length; i++) {
r -= this.w[i];
if (r <= 0) return i;
}
return this.w.length - 1;
}
}2Optimal (prefix sums + binary search)
constructor O(n), pickIndex O(log n)One pass builds the prefix sums; each pick is a single binary search.O(n)The prefix-sum array.Precompute prefix sums once, so index i owns the range (prefix[i - 1], prefix[i]]. The prefix array is strictly increasing because every weight is positive, so for a random r in [1, total] the owning index is the first one with prefix[i] >= r, which binary search finds in O(log n).
- Constructor: prefix[i] = w[0] + ... + w[i].
- pickIndex: r = random integer in [1, prefix[n - 1]].
- Binary search for the smallest i with prefix[i] >= r and return it.
class Solution {
private final int[] prefix;
private final Random rnd = new Random();
public Solution(int[] w) {
prefix = new int[w.length];
int sum = 0;
for (int i = 0; i < w.length; i++) {
sum += w[i];
prefix[i] = sum;
}
}
public int pickIndex() {
int r = rnd.nextInt(prefix[prefix.length - 1]) + 1;
int lo = 0, hi = prefix.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prefix[mid] < r) lo = mid + 1; else hi = mid;
}
return lo;
}
}import random
class Solution:
def __init__(self, w: List[int]):
self.prefix = []
s = 0
for x in w:
s += x
self.prefix.append(s)
def pickIndex(self) -> int:
r = random.randint(1, self.prefix[-1])
lo, hi = 0, len(self.prefix) - 1
while lo < hi:
mid = (lo + hi) // 2
if self.prefix[mid] < r:
lo = mid + 1
else:
hi = mid
return loclass Solution {
vector<int> prefix;
mt19937 gen{random_device{}()};
public:
Solution(vector<int>& w) {
int sum = 0;
for (int x : w) {
sum += x;
prefix.push_back(sum);
}
}
int pickIndex() {
int r = uniform_int_distribution<int>(1, prefix.back())(gen);
int lo = 0, hi = prefix.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prefix[mid] < r) lo = mid + 1; else hi = mid;
}
return lo;
}
};class Solution {
constructor(w) {
this.prefix = [];
let sum = 0;
for (const x of w) {
sum += x;
this.prefix.push(sum);
}
}
pickIndex() {
const p = this.prefix;
const r = Math.floor(Math.random() * p[p.length - 1]) + 1;
let lo = 0, hi = p.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (p[mid] < r) lo = mid + 1; else hi = mid;
}
return lo;
}
}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.