Random Pick with Weight
mediumTime: O(log n)Space: O(n)
Signals to notice
pick random index weighted by probabilityprefix sum + binary searchweighted random selection
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.
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.
Easy way to go wrong
Off-by-one in binary search — use leftmost insertion point (bisect_left) to map correctly.