# LC528 - Random Pick with Weight
## PrefixSum + Binary Search

class Solution {
    
    private Random random;
    private int[] prefixSum;

    public Solution(int[] w) {
        int length = w.length;
        random = new Random();
        // prefixSum[i] = w[0] + ... + w[i - 1]
        prefixSum = new int[length + 1]; 
        for (int i = 1; i <= length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i - 1];
        }
    }
    
    public int pickIndex() {
        int length = prefixSum.length;
        int target = random.nextInt(prefixSum[length - 1]) + 1;
        return smallestLargerThanOrEqualTo(target) - 1;
    }
    
    private int smallestLargerThanOrEqualTo(int target) {
        if (prefixSum.length == 0) {
            return -1;
        }
        
        int left = 0;
        int right = prefixSum.length - 1;
        while (left + 1 < right) {
            int middle = left + (right - left) / 2;
            if (prefixSum[middle] >= target) {
                right = middle;
            } else {
                left = middle;
            }
        }
        
        if (prefixSum[left] >= target) {
            return left;
        }
        return right;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */