NeetCode #291LC-528MediumBinary Search
← Back to All Problems#291 · #528 · Random Pick with Weight(按权重随机选择)
📌 Problem Statement & Constraints
You are given a 0-indexed array of positive integers
w where w[i] describes the weight of index i. Implement pickIndex() which returns an index chosen at random with probability proportional to its weight. Constraints: 1 <= w.length <= 10^4, 1 <= w[i] <= 10^5; at most 10^4 calls.💡 Core Algorithmic Approaches
- Build a prefix-sum array of the weights. The total sum defines the sample space.
- Draw a uniform random integer in
[1, total]and binary search for the first prefix sum that is at least it. - The width of each index's interval in the prefix sums is exactly its weight, which gives the required proportionality.
- Using
bisect_lefton the prefix array is O(log n) per call.
💻 Benchmark Python3 Implementation
class Solution:
def __init__(self, w: List[int]):
from bisect import bisect_left
self.prefix = []
cur = 0
for x in w:
cur += x
self.prefix.append(cur) # cumulative weights
self.total = cur
def pickIndex(self) -> int:
import random
from bisect import bisect_left
target = random.randint(1, self.total) # uniform in [1, total]
return bisect_left(self.prefix, target) # first prefix >= target⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) preprocessing, O(log n) per pick.
💾 Space Complexity
O(n) for the prefix array.
⚠️ Interview Pitfalls & Follow-ups
- Drawing
random.random() * totaland usingbisect_left: the half-open interval handling is easy to get wrong; a uniform integer in[1, total]withbisect_leftis exact. - Using
random.randint(0, total): the value 0 has no corresponding interval and would return index 0 spuriously. - Linear scanning of the prefix array: O(n) per pick.
- Normalising the weights to probabilities first: unnecessary and introduces floating-point error.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.