Random Pick with Weight

This approach significantly optimizes the picking process. While the setup in the constructor remains the same—calculating prefix sums—it leverages a key property of the prefixSums array: it is sorted in non-decreasing order. This allows us to use a much faster binary search algorithm, instead of a linear scan, to find the correct index for a given random value. This reduces the time complexity of each pickIndex call from linear to logarithmic.

• The constructor logic is the same: create a prefixSums array by calculating the cumulative sums of weights.
• In pickIndex, generate a random integer target from 1 to totalSum.
• Instead of a linear scan, perform a binary search on the prefixSums array to find the target index.
• Initialize low = 0, high = prefixSums.length - 1, and a result variable.
• While low <= high, calculate the middle index mid.
• If prefixSums[mid] >= target, mid is a potential answer. Store it in result and search for a potentially smaller index in the left half by setting high = mid - 1.
• Otherwise, if prefixSums[mid] < target, the answer must be in the right half, so set low = mid + 1.
• After the loop, result will hold the smallest index i such that prefixSums[i] >= target.

Constructor (Solution(int[] w))

The constructor implementation is identical to the linear search approach. We compute a prefixSums array where prefixSums[i] holds the sum of weights from w[0] to w[i], and we store the totalSum.

pickIndex() Method

The key improvement is in this method. After generating a random target between 1 and totalSum, we use binary search to find the index. We are looking for the smallest index i such that prefixSums[i] >= target. This is a classic 'lower bound' search problem.

The binary search works by repeatedly dividing the search interval in half. If the value at the middle of the interval is less than the target, we know the target must be in the right half. If the value is greater than or equal to the target, the middle element could be our answer, but we continue searching in the left half to see if a smaller index also satisfies the condition. This process efficiently hones in on the correct index.

class Solution {
    private int[] prefixSums;
    private int totalSum;
    private java.util.Random rand = new java.util.Random();

    public Solution(int[] w) {
        this.prefixSums = new int[w.length];
        int currentSum = 0;
        for (int i = 0; i < w.length; ++i) {
            currentSum += w[i];
            this.prefixSums[i] = currentSum;
        }
        this.totalSum = currentSum;
    }

    public int pickIndex() {
        // Generate a random number between 1 and totalSum (inclusive)
        int target = rand.nextInt(totalSum) + 1;
        
        // Binary search to find the index
        int low = 0;
        int high = prefixSums.length - 1;
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (target > prefixSums[mid]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}