Random Pick with Weight

Was this helpful?

Medium•array•Expected: O(log n) time, O(n) space

binary-searchprefix-sum

Problem

Given an array of positive integers w, implement pickIndex() that randomly picks an index in proportion to its weight.

Example 1:

Input: w = [1, 3]
       pickIndex() // returns 0 with probability 1/4, 1 with probability 3/4

Example 2:

Input: w = [1, 1, 1]
       pickIndex() // returns 0, 1, or 2 each with probability 1/3

Reference solution unlocks after your first submission

Language: