Random Pick with Weight

LeetCode Problem #528 (Medium)

Problem Statement

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

For example, given an input list of values [1, 9], when we pick up a number out of it, the chance is that 9 times out of 10 we should pick the number 9 as the answer.

Note:

1 <= w.length <= 10000

1 <= w[i] <= 10^5

pickIndex will be called at most 10000 times.

Testcases

Input Syntax Explanation

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

The input is two lists: the subroutines called and their arguments. 
Solution's constructor has one argument, the array w. pickIndex has no arguments. 
Arguments are always wrapped with a list, even if there aren't any.

Prerequisite Knowledge

Modulus Operation

a % b when a > b

If a = 16 and b = 15,

16 % 15 = 1 since 15 * 1 + 1 = 16

a % b when a < b

If a = 6 and b = 15,

6 % 15 = 6 since 15 * 0 + 6 = 6

Binary Search

Binary search is an efficient searching algorithm which is performed on a sorted array by repeatedly dividing the search interval in half, where the original size of the search interval is the size of the array.

The target value is compared with the mid-value of the seach interval during each iteration, and the decision of whether to continue searching in the left half or right half is taken based on whether the target value is greater than the mid-value or less than the mid-value.

Since the array is already sorted, if the target value is less than the mid value, we know that the value can only be found in the left half of the array, which contains elements which are less than the mid-value. Similarly, if the target value is greater than the mid-value, it is only reasonable to assume that it will be located in the right half of the array, where the elements are greater than the mid-value.

target < mid -> search left half

target > mid -> search right half

Algorithm

Let left = 0 and right = size - 1.
Calculate the mid value of the sorted array by taking the rounded average of left and right.
Compare the target value with the mid value.
If the target value has been found, return the index.
If the target value is less than the mid value, set left = mid + 1 (search in left half).
If the target value is greater than the mid value, set right = mid - 1 (search in right half).
Repeat until the value is found or the array becomes empty.

Computing Middle Index

To find the index of the middle element during each iteration, we must find the rounded average of the left (minimum) and right (maximum) pointer values.

Conventionally, we would compute this as:

mid = (left + right) / 2

However, if we take overflow into consideration, then this computation would not work. If, for example, the maximum value that an integer can have is 100, and our left and right values are 40 and 80.

Using the intuitive formula, when we add left and right, we get:

left + right = 40 + 80 = 120 (overflow)
mid = 120 / 2 = 60 (mid value)

120 is clearly greater than 100, which is the maximum range of the particular integer. This is an overflow.

Now, if we apply the formula:

mid = left + (right - left) / 2

Since right > left, when we subtract the value of left from right, the result will always be a smaller number, thus effectively preventing overflow.

Now when we compute the mid-value, we get:

mid = 40 + (80 - 40) / 2
mid = 40 + (40 / 2)
mid = 60

Since 40 is within the bounds of the integer range, no overflow occurs.

Problem Explanation

Example:

Consider an array of weights: [3, 7, 1, 4].

Each value in the array corresponds to the frequency of occurrence of the element at that index value.

Element 0 occurs 3 times.

Element 1 occurs 7 times.

Element 2 occurs 1 time.

Element 3 occurs 4 times.

[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3]

The total sum of weights is 3 + 7 + 1 + 4 = 15.

We can calculate the probability of each element occurring:

Element 0: 3 / 15 
Element 1: 7 / 15 
Element 2: 1 / 15 
Element 3: 4 / 15

We need to generate the probability mass function of each index.

Suppose we have an array of 15 equal elements.

Element 0 occupies index values from 0->2 (3 elements)
Element 1 occupies index values from 3->9 (7 elements)
Element 2 occupies index values from 10->10 (1 element)
Element 3 occupies index values from 11->14 (4 elements)

To get an index value and the corresponding mapping to the respective element, we generate a random number and take its modulo to 15.

Assume the random number is 6.

6 % 15 = 9

Therefore, it is in the range [3-9] so it is mapped back to Element 1.

Algorithm

Binary Search Approach

1. Store the lower and upper range of each weight according to its occurrence.

2. Generate a random index value and perform modulus with the total number of elements.

3. Search through the vector storing ranges using binary search to find the index value.

Code

// Initialize a variable to store the number of elements in the new vector
int n = 0;
// Vector to store the range of each element according to its frequency of occurrence
vector<pair<int, int>> range;

Solution(vector<int>& w) {
    for(int weight: w) {
        // Store the starting and ending range of each weight value
        range.push_back({n, n + weight - 1});
        n += weight;
    }
}
    
int pickIndex() {
    // Generate a random index value and perform modulus with the total number of elements in the vector
    int index = rand() % n;
    // Perform binary search to find the index value
        int left = 0, right = range.size() - 1;
        while(left <= right) {
        int mid = (left + right) / 2;
        // Check if the index value falls within a particular range
        if(range[mid].first <= index && range[mid].second >= index) {
            return mid;
        }
        if(range[mid].first > index) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return left;
}