---
tags: leetcode
---

# [528. Random Pick with Weight](https://leetcode.com/problems/random-pick-with-weight/)
---
# My Solution
## The Key Idea for Solving This Coding Question
Example:
$w = [1, 3]$ => $data = [1, 4]$
Therefore, $x$ can be $0$, $1$, $2$ or $3$.
We map $x = 0$ to $data[0]$ which is $1$.
$x = 1, 2, 3$ to $data[1]$ which is $4$.
Therefore, we should find a value in $data$ that is greater than $x$.
## C++ Code

class Solution {
public:
    Solution(vector<int> &w) {
        prefixSum.resize(w.size());
        prefixSum[0] = w[0];
        for (int i = 1; i < prefixSum.size(); ++i) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
    }

    int pickIndex() {
        int x = rand() % prefixSum.back();

        // Use binary search to find a prefix sum (prefixSum[middle])
        // that is greater than x.
        int left = 0, right = prefixSum.size() - 1;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (prefixSum[middle] <= x) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        if (prefixSum[left] <= x) {
            ++left;
        }

        return left;
    }

private:
    vector<int> prefixSum;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

## Time Complexity
* `Sloution`
$O(1)$
* `pickIndex`
$O(logn)$
$n$ is the length of `w`.
## Space Complexity
* `Sloution`
$O(n)$
* `pickIndex`
$O(1)$
# Miscellane
<!--
# Test Cases

["Solution","pickIndex"]
[[[1]],[]]

["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]

* Wrong Answer: https://leetcode.com/submissions/detail/716101304/testcase/
-->