Problem Statement
Random Pick with Weight
You are given an array w where w[i] is the weight of index i. You need a function called pickIndex() that picks an index at random, but not evenly. The bigger an index's weight, the more often it should get picked. If index A has weight 3 and index B has weight 1, then A should come up 3 times as often as B. Here is the picture to hold in your head. Imagine a raffle. Every weight is a number of tickets. Index 0 with weight 1 gets 1 ticket, index 1 with weight 3 gets 3 tickets. You drop all the tickets in a bag, draw one, and see whose ticket it is. The trick we use is this: instead of a real bag, we lay all the tickets out in a line and number them 1, 2, 3, and so on. Then we pick a random number in that line and figure out which index owns that spot. To find the owner fast, we use binary search, which is a way to find something in a sorted list by repeatedly cutting the search range in half instead of checking every item one by one.
Signals to notice
Brute force first
Generate a flat array with duplicates proportional to weight — O(sum) space.
The key insight
Build prefix sum array. Generate random number in [1, totalWeight]. Binary search for the index. O(n) init, O(log n) per pick.
Trace it on w=[1,2,3], target=5 (random in [1,6])
init: prefix=[1,3,6], total=6 pick: target=5; left=0, right=2 mid=1, prefix[1]=3 < 5 -> left=mid+1=2 left=2, right=2 -> loop ends (left<right false) return left=2 (target 5 falls in range [4,6] -> index 2, weight 3)
What must stay true
The prefix sum array divides [1, total] into ranges proportional to weights. Binary search maps a random number to the correct range/index.
Shape of the loop
build prefix sums; total = prefix[-1] target = random_int(1, total) left, right = 0, len(prefix)-1 while left < right: mid = (left+right)//2 if prefix[mid] < target: left = mid+1 else: right = mid return left
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Off-by-one in binary search — use leftmost insertion point (bisect_left) to map correctly.