Coding Interview PatternsRandom Pick with Weight
MediumModified Binary Search
Random Pick with Weight
Explanation & Solution
Description
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).
For testing purposes, you receive w and an array of targets (each in range [1, sum(w)]). For each target, return the index that would be selected by binary searching the prefix sum array.
Input:w = [1, 3], targets = [1, 2, 3, 4]
0
1
1
3
0
1
1
2
2
3
3
4
Output:[0, 1, 1, 1]
0
0
1
1
2
1
3
1
Explanation: Prefix sums = [1, 4]. Target 1 → index 0, targets 2–4 → index 1.
Constraints
1 <= w.length <= 10^41 <= w[i] <= 10^51 <= targets[i] <= sum(w)
Approach
Modified Binary Search pattern
1. Build the Prefix Sum Array
- Compute cumulative sums:
prefix[i] = w[0] + w[1] + ... + w[i]. - Each index
i"owns" the range(prefix[i-1], prefix[i]].
2. For Each Target, Binary Search
- Find the smallest index where
prefix[index] >= target. - This is the standard left-bound binary search.
3. Why This Works
- A random number in
[1, totalSum]falls into indexi's range with probability proportional tow[i]. - Binary search on the prefix sum array efficiently maps the random number to the correct index.
🧠 Key Insight
- The prefix sum creates non-overlapping ranges proportional to weights. Binary search on this array is the standard approach for weighted random selection.
Time
O(n) to build prefix sums, O(log n) per pick.Space
O(n) for the prefix sum array.Visualization
Input:
[1, 3]
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
11 steps