#528

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Random Pick with Weight

Random Pick with Weight requires implementing a probabilistic index picker using prefix sums and binary search efficiently.

array math binary search prefix sum randomized

Problem Statement

You are given a 0-indexed array of positive integers w where each w[i] represents the weight of index i. Your task is to implement a function pickIndex() that returns an index in the range [0, w.length - 1] randomly, with the probability of selecting index i being w[i] divided by the total sum of all weights.

For example, given w = [1,3], pickIndex() should return 0 with probability 1/4 and 1 with probability 3/4. Multiple calls to pickIndex() should reflect this distribution. You must also ensure that pickIndex() is efficient enough for up to 10^4 calls, and the array can contain up to 10^4 elements with weights up to 10^5.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Solution","pickIndex"] [[[1]],[]] Output [null,0]

Explanation Solution solution = new Solution([1]); solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Example 2

Input: See original problem statement.

Output: See original problem statement.

Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0]

Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.

Constraints

1 <= w.length <= 104
1 <= w[i] <= 105
pickIndex will be called at most 104 times.

Solution Approach

Compute Prefix Sum Array

First, generate a prefix sum array where each element at index i contains the sum of weights from w[0] to w[i]. This allows us to map each index to a cumulative weight range, forming the foundation for weighted random selection.

Use Random Number Generation

Generate a random integer between 1 and the total sum of weights. This random number represents a target in the cumulative weight range, effectively choosing a weighted position.

Binary Search for Target Index

Apply binary search over the prefix sum array to find the smallest index whose prefix sum is greater than or equal to the random target. This step ensures pickIndex() runs in O(log n) time while maintaining the correct weighted probabilities.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for preprocessing prefix sums and O(log n) for each pickIndex call due to binary search. Space complexity is O(n) to store the prefix sum array.

What Interviewers Usually Probe

Mentions of weighted probability or random selection indicate candidate understanding of array-to-probability mapping.
Candidate suggests prefix sums before random index generation showing grasp of cumulative distribution mapping.
Binary search on the prefix sum demonstrates correct application of the problem's primary pattern.

Common Pitfalls or Variants

Common pitfalls

Using random number generation directly on indices without weight adjustment leads to incorrect probabilities.
Iterating through weights linearly for each pickIndex causes O(n) per query instead of O(log n).
Off-by-one errors when mapping random numbers to prefix sum ranges can skew probability distribution.

Follow-up variants

Changing the weight array dynamically requires segment trees or Fenwick trees for updates while keeping efficient pickIndex.
Picking k indices instead of one can be handled by repeated weighted selection with care to avoid repeated selection bias.
Handling very large weights may need careful data type selection or scaling to prevent integer overflow during prefix sum computation.

FAQ

How does Random Pick with Weight use prefix sums?

Prefix sums map each index to a cumulative weight range, enabling O(log n) binary search to select an index with correct probability.

Can pickIndex() run efficiently for large arrays?

Yes, preprocessing prefix sums is O(n) and each pickIndex call is O(log n), suitable for up to 10^4 calls.

What happens if weights are very large?

Use data types that prevent integer overflow, or scale weights appropriately to maintain accuracy in cumulative sums.

Is binary search necessary in Random Pick with Weight?

Binary search is the core pattern to efficiently locate the target index within cumulative weight ranges instead of linear scanning.

Can weights change after initialization?

If weights change, prefix sums must be updated, potentially with a segment tree or Fenwick tree to maintain O(log n) pickIndex calls.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def __init__(self, w: List[int]):
        self.s = [0]
        for c in w:
            self.s.append(self.s[-1] + c)

    def pickIndex(self) -> int:
        x = random.randint(1, self.s[-1])
        left, right = 1, len(self.s) - 1
        while left < right:
            mid = (left + right) >> 1
            if self.s[mid] >= x:
                right = mid
            else:
                left = mid + 1
        return left - 1


# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

Continue Practicing

#497 random point in non overlapping rectangles #710 random pick with blacklist #523 continuous subarray sum