Weighted Random

class Solution {
    
    private int[][] ranges;
    private int totalSum;
    private Random random;

    public Solution(int[] weights) {
        ranges = new int[weights.length][2];

        for (int i=0, current = 0; i < weights.length; i++) {
            ranges[i] = new int[]{current, current + weights[i]};
            current = current + weights[i];
            totalSum += weights[i];
        }

        random = new Random();
    }

    public int pickIndex() {
        int randomNumber = random.nextInt(totalSum);
        int left = 0, right = ranges.length-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int[] range = ranges[mid];
            if (range[0] <= randomNumber && randomNumber < range[1]) {
                return mid;
            } else if (randomNumber < range[0]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        throw new AssertionError("Should not reach here");
    }
}