Math - Random Pick with Weight

Given a list of positive integers w where w[i] is the weight of ith index, implement pickIndex() to randomly pick an index such that probability of picking index i is proportional to w[i].

Input: w=[1,3], pickIndex can return 0 (25%) or 1 (75%)

Build a prefix sum array. Use random to get a number in [1, total]. Binary search for the first prefix sum >= random number.

prefixSum[i] = sum of w[0..i].
On pickIndex: r = random(1, totalSum).
Binary search for first index where prefixSum[i] >= r.
Return that index.

import java.util.*; class Solution { int[] prefix; int total; Random rand = new Random(); public Solution(int[] w) { prefix = new int[w.length]; prefix[0] = w[0]; for (int i = 1; i < w.length; i++) prefix[i] = prefix[i-1] + w[i]; total = prefix[w.length-1]; } public int pickIndex() { int r = rand.nextInt(total) + 1; int lo=0, hi=prefix.length-1; while (lo < hi) { int mid = lo+(hi-lo)/2; if (prefix[mid] < r) lo=mid+1; else hi=mid; } return lo; } }

Time Complexity: pickIndex: O(log N)
Space Complexity: O(N)