Title: Random Pick with Weights
In this guide, you’ll learn how to solve the Random Pick with Weights problem in Java, a classic array and probability interview question. Given an array of positive integer weights, the goal is to design a class that picks a random index, where the probability of picking a given index is proportional to its weight.
This problem shows up often in interviews because it combines prefix sums, binary search, and a careful understanding of how random number generation maps to probability. Let’s explore how to build a pickIndex() method that runs in O(log n) time after a one-time O(n) setup.
Understanding the Problem
You are given an integer array weights where weights[i] describes the weight of index i. You must implement a class with a method pickIndex() that randomly picks an index in the range [0, weights.length - 1], such that the probability of picking index i equals weights[i] / sum(weights).
For example, if weights = [1, 3], index 0 should be picked with probability 1/4 and index 1 should be picked with probability 3/4. Constructing the object may do preprocessing work, but each call to pickIndex() should be fast, ideally faster than scanning the whole array.
The key insight is that weights can be converted into contiguous, non-overlapping ranges whose lengths are proportional to the weights themselves. Picking a random index then becomes equivalent to picking a random point along the total length and finding which range it falls into.
Approach: Prefix Sums with Binary Search
The approach splits into two phases, a one-time setup that builds a prefix sum array, and a fast lookup that uses binary search to map a random draw to an index.
- Build a
prefixSumsarray whereprefixSums[i]stores the cumulative sum ofweights[0..i]. - Store the last value of
prefixSumsastotalSum, the sum of every weight. - In
pickIndex(), draw a random integertargetin the range 1 tototalSuminclusive. - Binary search
prefixSumsfor the smallest indexisuch thatprefixSums[i] >= target. - Return that index
ias the picked index. - Repeat steps 3 to 5 on every call to
pickIndex(), since the constructor’s work only happens once.
Java Program
Here is a complete, compilable implementation of RandomPickWithWeights in Java:
import java.util.Random;
public class RandomPickWithWeights {
private int[] prefixSums;
private int totalSum;
private Random random;
public RandomPickWithWeights(int[] weights) {
this.prefixSums = new int[weights.length];
this.random = new Random();
int sum = 0;
for (int i = 0; i < weights.length; i++) {
sum += weights[i];
prefixSums[i] = sum;
}
this.totalSum = sum;
}
public int pickIndex() {
int target = random.nextInt(totalSum) + 1;
int low = 0;
int high = prefixSums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (prefixSums[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
public static void main(String[] args) {
int[] weights = {1, 3, 2, 4};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
int[] counts = new int[weights.length];
int trials = 100000;
for (int i = 0; i < trials; i++) {
int index = picker.pickIndex();
counts[index]++;
}
for (int i = 0; i < counts.length; i++) {
double percentage = (counts[i] * 100.0) / trials;
System.out.println("Index " + i + " picked " + counts[i] + " times (" + percentage + "%)");
}
}
}Explanation of the Program
prefixSumsis built once inside the constructor by running a cumulative sum overweights, soprefixSums[i]holds the sum of every weight up to and including indexi.totalSumstores the final cumulative value, the sum of every weight, and it defines the upper bound for the random target.pickIndex()drawstargetfrom 1 tototalSumusingrandom.nextInt(totalSum) + 1, sincenextInt(bound)alone returns a value in[0, bound).- The binary search narrows
lowandhighuntil it finds the smallest index whoseprefixSumsvalue is greater than or equal totarget, which is exactly the interval containingtarget. - Because the constructor does all the O(n) work once, every call to
pickIndex()only pays for an O(log n) binary search.
Step-by-Step Trace
Consider weights = {2, 5, 1}, which gives prefixSums = {2, 7, 8} and totalSum = 8. Suppose the random draw produces target = 6. Since 6 falls inside the interval (3, 7] owned by weights[1] = 5, the expected result of pickIndex() is index 1.
| Iteration | low | high | mid | prefixSums[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 7 | 7 >= 6, so high = mid = 1 |
| 2 | 0 | 1 | 0 | 2 | 2 < 6, so low = mid + 1 = 1 |
| 3 | 1 | 1 | – | – | low == high, loop ends, return 1 |
At the end of each iteration, the search range [low, high] still contains the smallest index whose prefixSums value is greater than or equal to target, so the loop never discards the correct answer.
Examples
Example 1: Equal Weights (Uniform Distribution)
When every weight is equal, every index should be picked with roughly the same frequency.
int[] weights = {1, 1, 1, 1};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
// prefixSums = {1, 2, 3, 4}, totalSum = 4
// Over many calls, pickIndex() returns 0, 1, 2, and 3 with roughly equal frequency (about 25% each)Example 2: Skewed Weights
When one weight dominates the others, it should be picked far more often.
int[] weights = {1, 9};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
// prefixSums = {1, 10}, totalSum = 10
// Index 1 is picked roughly 90% of the time and index 0 roughly 10% of the time,
// because 9 of the 10 possible target values (2 through 10) fall inside index 1's intervalExample 3: Single-Element Weights
With only one weight in the array, every call must return the same index.
int[] weights = {5};
RandomPickWithWeights picker = new RandomPickWithWeights(weights);
int index = picker.pickIndex();
// prefixSums = {5}, totalSum = 5
// index is always 0, since there is only one interval and every possible target falls inside itCommon Mistakes to Avoid
These are the mistakes candidates actually make when implementing weighted random picking, not generic programming advice.
- Drawing target from 0 instead of 1 – calling
random.nextInt(totalSum)without the+ 1letstargetequal 0, which falls outside every interval and silently skews the distribution. Always drawtargetin the range 1 tototalSuminclusive. - Replacing binary search with a linear scan – looping through
prefixSumsfrom the start still finds the correct index, but it costs O(n) per call and defeats the purpose of precomputing prefix sums. Use binary search sopickIndex()runs in O(log n). - Flipping the binary search comparison – writing
prefixSums[mid] <= targetinstead ofprefixSums[mid] < targetmoveshightoo aggressively and can return an index one position too low near interval boundaries. Keep the comparison asprefixSums[mid] < targetwhen deciding to movelowup. - Rebuilding prefixSums inside pickIndex() - recomputing the cumulative sums on every call wastes the O(n) work the constructor already finished once. Build
prefixSumsonly inside the constructor and reuse it for every pick.
Edge Cases to Test
Walking through these boundary inputs unprompted is exactly the kind of habit interviewers look for.
- Single-element weights array
- All weights equal
- Highly skewed weights (one very large weight, others very small)
- Zero weight at some index
- Sum of weights overflowing int range
- Negative or zero total weight (invalid input)
- Large number of repeated pickIndex() calls
- Large weights array (binary search performance under heavy use)
Additional Considerations
The constructor runs in O(n) time and O(n) space, since it builds one prefix sum array the same length as weights. This cost is paid only once, no matter how many times pickIndex() is called afterward.
Each call to pickIndex() runs in O(log n) time with O(1) extra space, thanks to binary search. This is a significant improvement over a naive linear scan, which would cost O(n) per call.
If the sum of weights can exceed Integer.MAX_VALUE, switch prefixSums and totalSum to long, and replace random.nextInt(totalSum) with ThreadLocalRandom.current().nextLong(totalSum) to avoid overflow.
An alternative is the alias method, which achieves O(1) time per pick after an O(n) setup. It is faster per call but considerably more complex to implement correctly, so the prefix sum and binary search approach remains the standard interview-friendly solution.
Interview Follow-up Questions
A base solution is only the first ten minutes of the interview. Here are the follow-up questions that probe deeper.
- What if weights can change after the object is constructed? - maintain the weights in a Fenwick tree (binary indexed tree) so both updating a weight and querying a prefix sum run in O(log n), instead of rebuilding the whole
prefixSumsarray. - What if an index must never be picked twice? - after picking index i, zero out
weights[i]and subtract it fromtotalSum, updating the Fenwick tree sopickIndex()never lands on that interval again. - What if the weights arrive as an unbounded stream? - use weighted reservoir sampling (the A-Res algorithm), assigning each incoming item a key based on a random draw and its weight, and keeping only the item with the largest key seen so far.
- What if totalSum can exceed Integer.MAX_VALUE? - store
prefixSumsandtotalSumaslong, and useThreadLocalRandom.current().nextLong(totalSum)instead ofRandom.nextInt(totalSum)to avoid overflow and stay safe under concurrent calls.
Conclusion
The Random Pick with Weights problem is a great example of turning a probability requirement into a search problem. By converting weights into cumulative ranges and using binary search to map a random draw onto those ranges, pickIndex() stays fast even as the number of picks grows.
Try adapting this same prefix sum and binary search pattern to other weighted selection problems, such as weighted sampling from a stream or picking a random node in a tree. You can learn more about array-based interview problems like this one on our Arrays category page.



