AlgoMaster Logo

Random Pick with Weight

Last Updated: April 3, 2026

medium
3 min read

Understanding the Problem

We need to build a system that picks random indices, but not uniformly. Each index has a weight, and heavier indices should be picked more often. If index 0 has weight 1 and index 1 has weight 3, then index 1 should be picked 3 times as often as index 0.

Think of it like a number line. If the weights are [1, 3, 2], the total is 6. Index 0 "owns" 1 unit of that line, index 1 owns 3 units, and index 2 owns 2 units. If you throw a dart at a random point on that number line, the probability of hitting each index's segment is proportional to its weight.

The real question is: how do we efficiently map a random number to the correct index? A naive approach would scan through the weights each time, but we can do better with prefix sums and binary search.

Key Constraints:

  • 1 <= w.length <= 10^4 → Up to 10,000 weights. We need the constructor to be efficient, but O(n) preprocessing is fine.
  • 1 <= w[i] <= 10^5 → All weights are positive. No zero-weight indices, which simplifies things since every index has a non-zero probability.
  • pickIndex will be called at most 10^4 times → Each call should be fast. O(n) per call means up to 10^8 operations total, which is borderline. O(log n) per call would be much safer.

Approach 1: Linear Scan with Prefix Sum

Intuition

Let's start with the most straightforward way to solve this. Build a prefix sum array from the weights, generate a random number between 1 and the total weight, then scan through the prefix sums to find which index that random number falls into.

The prefix sum array transforms the problem into a range lookup. If the weights are [1, 3, 2], the prefix sums are [1, 4, 6]. Index 0 covers the range [1, 1], index 1 covers [2, 4], and index 2 covers [5, 6]. A random number of 3 falls into index 1's range, so we return 1.

Algorithm

  1. In the constructor, build a prefix sum array from the weights.
  2. In pickIndex(), generate a random integer in the range [1, totalWeight].
  3. Scan through the prefix sum array. Return the first index where prefixSum[i] >= randomTarget.

Example Walkthrough

1Prefix sums built from weights [1, 3, 2]. Random target = 3
0
1
i
1
4
2
6
1/4

Code

The linear scan works but doesn't take advantage of the fact that the prefix sum array is sorted. Since it's always in increasing order, we can use binary search to find the target range in O(log n) instead of O(n).

Approach 2: Prefix Sum + Binary Search (Optimal)

Intuition

The key observation is that the prefix sum array is always sorted in increasing order (since all weights are positive). This means we can replace the linear scan with binary search.

Instead of checking each prefix sum one by one, we use binary search to find the smallest index where prefixSum[i] >= target. This is the lower bound pattern, exactly the same binary search template used in problems like Search Insert Position.

Here's the mental model: imagine a roulette wheel where each index gets a slice proportional to its weight. The prefix sum array defines the boundaries of each slice. When we spin the wheel (generate a random number), binary search tells us which slice the ball landed on in O(log n) time.

Algorithm

  1. In the constructor, build a prefix sum array from the weights. Store the total weight.
  2. In pickIndex():
    • Generate a random integer target in the range [1, totalWeight].
    • Use binary search to find the smallest index i where prefixSum[i] >= target.
    • Return that index.

Example Walkthrough

1Prefix sums: [1, 4, 6]. Binary search for first >= 5. left=0, right=3
0
1
left
1
4
2
6
search range
1/5

Code