LeetCode 528: Random Pick with Weight Solution in Python – A Step-by-Step Guide

What Is LeetCode 528: Random Pick with Weight?

In LeetCode 528: Random Pick with Weight, you’re given an array of positive integers w where each element represents the weight of index i, and you need to implement a class with a method pickIndex() that returns an index randomly, proportional to its weight. For example, with w = [1, 3], index 1 should be picked 3 times more often than index 0. This problem tests weighted random selection, related to LeetCode 398: Random Pick Index.

Problem Statement

• Input:
• Constructor: w (List[int])—array of weights.
• pickIndex(): No input.
• Output:
• Constructor: None.
• pickIndex(): Integer—random index based on weights.
• Rules: Probability of picking index i is w[i] / sum(w); weights are positive.

Constraints

• 1 <= w.length <= 10⁴
• 1 <= w[i] <= 10⁵
• pickIndex() called at most 10⁴ times.

Examples

• Input:
``` ["Solution","pickIndex"] [[1,3],[]] ```
• Output:
``` [null,1] ```
• Total weight = 4, P(0) = 1/4, P(1) = 3/4, likely 1.
• Input:
``` ["Solution","pickIndex","pickIndex","pickIndex"] [[1,2,3],[]] ```
• Output:
``` [null,2,1,0] ```
• Total weight = 6, P(0) = 1/6, P(1) = 2/6, P(2) = 3/6.

Understanding the Problem: Weighted Random Picks

To solve LeetCode 528: Random Pick with Weight in Python, we need a class that initializes with weights and provides a pickIndex() method to return an index with probability proportional to its weight. A naive approach might use a simple random choice with weights, but with up to 10⁴ calls, we need efficiency. We’ll explore:

• Best Solution (Prefix Sum with Binary Search): O(n) init, O(log n) per pick, O(n) space—fast and scalable.
• Alternative Solution (Cumulative Probability with Linear Scan): O(n) init, O(n) per pick, O(n) space—simple but slower.

Let’s dive into the prefix sum solution with a friendly breakdown!

Best Solution: Prefix Sum with Binary Search

Why Prefix Sum with Binary Search Wins

The prefix sum with binary search is the best for LeetCode 528 because it preprocesses weights into a cumulative sum array, then uses binary search to pick an index in O(log n) time per call, with O(n) space and O(n) initialization. It’s like turning a weighted wheel into a number line and quickly finding where a random dart lands!

How It Works

Think of this as a weighted number line:

• Step 1: Compute Prefix Sums:
• prefix[i] = sum of weights from 0 to i.
• Total weight = prefix[-1].
• Step 2: Random Target:
• Generate a random number between 1 and total weight.
• Step 3: Binary Search:
• Find the smallest index where prefix[i] >= target.
• This index has probability proportional to its weight.
• Why It Works:
• Prefix sums map weights to intervals.
• Binary search finds the interval efficiently.

It’s like a weighted dartboard picker!

Step-by-Step Example

Example: w = [1, 3, 2]

• Step 1: Prefix sums:
• prefix = [1, 4, 6], total = 6.
• Step 2: pickIndex():
• Random target = 3 (1 to 6).
• Step 3: Binary search:
• left = 0, right = 2:
• mid = 1, prefix[1] = 4 >= 3, right = 0.
• mid = 0, prefix[0] = 1 < 3, left = 1.
• Return 1 (weight 3 covers 2 to 4).
• Result: Likely 1 (P(0) = 1/6, P(1) = 3/6, P(2) = 2/6).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

import random
import bisect

class Solution:
    def __init__(self, w: List[int]):
        # Step 1: Compute prefix sums
        self.prefix = []
        total = 0
        for weight in w:
            total += weight
            self.prefix.append(total)
        self.total = total

    def pickIndex(self) -> int:
        # Step 2: Generate random target
        target = random.randint(1, self.total)

        # Step 3: Binary search for index
        return bisect.bisect_left(self.prefix, target)

• Lines 6-10: Constructor:
• Build prefix sum array, store total.
• Lines 13-14: pickIndex():
• Random number from 1 to total weight.
• Line 17: Binary search finds leftmost index where prefix >= target.
• Time Complexity: O(n) init, O(log n) per pick.
• Space Complexity: O(n)—prefix array.

It’s like a weighted index finder!

Alternative Solution: Cumulative Probability with Linear Scan

Why an Alternative Approach?

The cumulative probability with linear scan solution uses a similar prefix sum array but scans linearly to find the target index. It’s O(n) init and O(n) per pick with O(n) space—simpler to code but slower per call. Great for understanding the basics!

How It Works

Picture this as a weighted ladder:

• Step 1: Compute prefix sums as in best solution.
• Step 2: Generate random target.
• Step 3: Scan prefix array until sum exceeds target.

It’s like a weighted ladder climber!

Step-by-Step Example

Example: w = [1, 3, 2]

• Step 1: prefix = [1, 4, 6], total = 6.
• Step 2: target = 5.
• Step 3: Scan:
• prefix[0] = 1 < 5.
• prefix[1] = 4 < 5.
• prefix[2] = 6 >= 5, return 2.
• Result: 2.

Code for Linear Scan Approach

import random

class Solution:
    def __init__(self, w: List[int]):
        self.prefix = []
        total = 0
        for weight in w:
            total += weight
            self.prefix.append(total)
        self.total = total

    def pickIndex(self) -> int:
        target = random.randint(1, self.total)
        for i in range(len(self.prefix)):
            if self.prefix[i] >= target:
                return i
        return 0  # Fallback (shouldn’t reach)

• Time Complexity: O(n) init, O(n) per pick.
• Space Complexity: O(n)—prefix array.

It’s a linear weighted picker!

Comparing the Two Solutions

• Prefix Sum with Binary Search (Best):
• Pros: O(log n) per pick, efficient.
• Cons: Binary search logic.
• Cumulative Probability with Linear Scan (Alternative):
• Pros: O(n) per pick, simpler.
• Cons: Slower per call.

Binary search wins for speed!

Additional Examples and Edge Cases

• [1]: Always 0.
• [1, 1]: 0 or 1 (50/50).
• [2, 3]: Bias toward 1.

Binary search handles them all!

Complexity Recap

• Binary Search: Init O(n), Pick O(log n), Space O(n).
• Linear Scan: Init O(n), Pick O(n), Space O(n).

Binary search’s the efficiency champ!

Key Takeaways

• Binary Search: Fast picks—learn at Python Basics!
• Linear Scan: Easy but slow.
• Randomization: Weights add fun.
• Python: Bisect shines!

Final Thoughts: Spin That Wheel!

LeetCode 528: Random Pick with Weight in Python is a delightful randomization challenge. Prefix sum with binary search is your fast track, while linear scan keeps it basic. Want more? Try LeetCode 398: Random Pick Index or LeetCode 384: Shuffle an Array. Ready to pick? Head to Solve LeetCode 528 on LeetCode and weigh those chances today!