> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Random Pick with Weight Python Solution

> Tested Python solution for LeetCode 528 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 528, Medium. Topics: Array, Math, Binary Search, Prefix Sum. [View on LeetCode](https://leetcode.com/problems/random-pick-with-weight/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 528   # by problem number
lcpy gen -s random_pick_with_weight   # by problem name
```

## Problem

You are given a **0-indexed** array of positive integers `w` where `w[i]` describes the weight of the `i^th` index.

You need to implement the function `pick_index()`, which **randomly** picks an index in the range `[0, w.length - 1]` (**inclusive**) and returns it. The **probability** of picking an index `i` is `w[i] / sum(w)`.

* For example, if `w = [1, 3]`, the probability of picking index `0` is `1 / (1 + 3) = 0.25` (i.e., `25%`), and the probability of picking index `1` is `3 / (1 + 3) = 0.75` (i.e., `75%`).

### Examples

```
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.
```

```
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.
```

### Constraints

* 1 \<= w\.length \<= 10^4
* 1 \<= w\[i] \<= 10^5
* `pickIndex` will be called at most 10^4 times.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/random_pick_with_weight/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/random_pick_with_weight/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import bisect
import random


class Solution:
    # Build prefix sums of weights. pick_index draws r in [1, total],
    # binary search for first prefix >= r. Each index i chosen with prob w[i]/sum.
    # Time: O(n) init, O(log n) pick_index
    # Space: O(n)
    def __init__(self, w: list[int]) -> None:
        self.prefix: list[int] = []
        running = 0
        for weight in w:
            running += weight
            self.prefix.append(running)
        self.total = running

    def pick_index(self) -> int:
        r = random.randint(1, self.total)
        return bisect.bisect_left(self.prefix, r)
```

## Complexity

| Time                            | Space |
| ------------------------------- | ----- |
| O(n) init, O(log n) pick\_index | O(n)  |

## Tags

[Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).