528. Random Pick with Weight LeetCode Solution

In this guide, you will get 528. Random Pick with Weight LeetCode Solution with the best time and space complexity. The solution to Random Pick with Weight problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Random Pick with Weight solution in C++
Random Pick with Weight solution in Java
Random Pick with Weight solution in Python
Additional Resources

528. Random Pick with WeightLeetCode Solution image

Problem Statement of Random Pick with Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.
You need to implement the function pickIndex(), 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%).

Example 1:

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.

Example 2:

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.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.

Constraints:

1 <= w.length <= 104
1 <= w[i] <= 105
pickIndex will be called at most 104 times.

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(n)

528. Random Pick with Weight LeetCode Solution in C++

class Solution {
 public:
  Solution(vector<int>& w) : prefix(w.size()) {
    partial_sum(w.begin(), w.end(), prefix.begin());
  }

  int pickIndex() {
    const int target = rand() % prefix.back();
    int l = 0;
    int r = prefix.size();

    while (l < r) {
      const int m = (l + r) / 2;
      if (prefix[m] > target)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  vector<int> prefix;
};
/* code provided by PROGIEZ */

528. Random Pick with Weight LeetCode Solution in Java

class Solution {
  public Solution(int[] w) {
    prefix = w;
    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1];
  }

  public int pickIndex() {
    final int target = rand.nextInt(prefix[prefix.length - 1]);
    int l = 0;
    int r = prefix.length;

    while (l < r) {
      final int m = (l + r) / 2;
      if (prefix[m] > target)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  private int[] prefix;
  private Random rand = new Random();
}
// code provided by PROGIEZ

528. Random Pick with Weight LeetCode Solution in Python

class Solution:
  def __init__(self, w: list[int]):
    self.prefix = list(itertools.accumulate(w))

  def pickIndex(self) -> int:
    target = random.randint(0, self.prefix[-1] - 1)
    return bisect.bisect_right(range(len(self.prefix)), target,
                               key=lambda m: self.prefix[m])
 # code by PROGIEZ