⚡Flashcard Drill➔
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

  1. Build a prefix-sum array of the weights. The total sum defines the sample space.
  2. Draw a uniform random integer in [1, total] and binary search for the first prefix sum that is at least it.
  3. The width of each index's interval in the prefix sums is exactly its weight, which gives the required proportionality.
  4. Using bisect_left on 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() * total and using bisect_left: the half-open interval handling is easy to get wrong; a uniform integer in [1, total] with bisect_left is 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems