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].

Example 1

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

Solution Approach

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.

Java

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)