Random Pick with Weight
mediumTime: O(log n)Space: O(n)
Recognize the pattern
pick random index weighted by probabilityprefix sum + binary searchweighted random selection
Brute force idea
Generate a flat array with duplicates proportional to weight — O(sum) space.
Better approach
Build prefix sum array. Generate random number in [1, totalWeight]. Binary search for the index. O(n) init, O(log n) per pick.
Key invariant
The prefix sum array divides [1, total] into ranges proportional to weights. Binary search maps a random number to the correct range/index.
Watch out for
Off-by-one in binary search — use leftmost insertion point (bisect_left) to map correctly.