528. Random Pick with Weight - Solution

The 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 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 <= 10⁴
1 <= w[i] <= 10⁵
pickIndex will be called at most 10⁴ times.

Approach overview

Problem Overview: You receive an array w where w[i] represents the weight of index i. The task is to implement pickIndex() so that the probability of picking index i is proportional to its weight. If w = [1,3], index 1 should be returned three times more often than index 0.

The core idea is to treat weights as ranges on a number line. If the total weight is 10, you randomly choose a number from [1,10] and determine which weight range contains that number.

Approach 1: Cumulative Sum with Linear Search (Initialization: O(n), Pick: O(n) time, O(n) space)

Build a prefix sum array where prefix[i] stores the total weight from index 0 to i. For example, weights [1,3,2] become prefix sums [1,4,6]. During pickIndex(), generate a random integer between 1 and the total weight. Iterate through the prefix array and return the first index where prefix[i] >= target. This works because each index occupies a proportional segment of the total range. The implementation is simple and demonstrates the key prefix sum idea, but every pick requires scanning the array.

Approach 2: Cumulative Sum with Binary Search (Initialization: O(n), Pick: O(log n) time, O(n) space)

The optimized approach keeps the same prefix sum array but replaces the linear scan with binary search. After generating a random number between 1 and the total weight, perform a lower-bound search on the prefix array to find the first index where the prefix value is greater than or equal to the target. Because the prefix array is sorted by construction, binary search finds the correct index in O(log n). This significantly improves performance when pickIndex() is called many times. The method combines array preprocessing, prefix sums, and randomized selection.

Recommended for interviews: The prefix sum with binary search solution is the expected answer. It shows that you recognize the weighted probability mapping and know how to convert it into a range search problem. Mentioning the linear scan approach first demonstrates understanding of the probability model, while the binary search optimization shows algorithmic maturity and awareness of repeated-query performance.

Approach 1: Cumulative Sum with Linear Search

This approach involves creating a cumulative sum array based on the provided weights. The idea is to convert the weight array into a cumulative distribution, where each element represents the summed result of all previous weights including the current one. When we generate a random number, we search for its position in this cumulative array to determine which index to return.

Python

import random

class Solution:

    def __init__(self, w):
        self.prefixSum = []
        current_sum = 0
        for weight in w:
            current_sum += weight
            self.prefixSum.append(current_sum)

    def pickIndex(self):
        target = random.randint(0, self.prefixSum[-1] - 1)
        for i, total in enumerate(self.prefixSum):
            if target < total:
                return i

Java

import java.util.*;

class Solution {
    private int[] prefixSum;
    private Random random;

    public Solution(int[] w) {
        prefixSum = new int[w.length];
        prefixSum[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
        random = new Random();
    }

    public int pickIndex() {
        int totalWeight = prefixSum[prefixSum.length - 1];
        int target = random.nextInt(totalWeight);
        for (int i = 0; i < prefixSum.length; i++) {
            if (target < prefixSum[i]) {
                return i;
            }
        }
        return -1; // Should never be reached
    }
}

C++

#include <vector>
#include <cstdlib>
using namespace std;

class Solution {
    vector<int> prefixSum;
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for (int weight : w) {
            sum += weight;
            prefixSum.push_back(sum);
        }
    }
    int pickIndex() {
        int totalWeight = prefixSum.back();
        int target = rand() % totalWeight;
        for (int i = 0; i < prefixSum.size(); i++) {
            if (target < prefixSum[i]) {
                return i;
            }
        }
        return -1; // Should never be reached
    }
};

JavaScript

class Solution {
    constructor(w) {
        this.prefixSum = [];
        let sum = 0;
        for (const weight of w) {
            sum += weight;
            this.prefixSum.push(sum);
        }
    }
    pickIndex() {
        const totalWeight = this.prefixSum[this.prefixSum.length - 1];
        const target = Math.floor(Math.random() * totalWeight);
        for (let i = 0; i < this.prefixSum.length; i++) {
            if (target < this.prefixSum[i]) {
                return i;
            }
        }
    }
}

typedef struct {
    int* prefixSum;
    int n;
} Solution;

Solution* solutionCreate(int* w, int wSize) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->prefixSum = (int*)malloc(sizeof(int) * wSize);
    obj->n = wSize;
    obj->prefixSum[0] = w[0];
    for (int i = 1; i < wSize; ++i) {
        obj->prefixSum[i] = obj->prefixSum[i - 1] + w[i];
    }
    return obj;
}

int solutionPickIndex(Solution* obj) {
    int totalWeight = obj->prefixSum[obj->n - 1];
    int target = rand() % totalWeight;
    for (int i = 0; i < obj->n; i++) {
        if (target < obj->prefixSum[i]) {
            return i;
        }
    }
    return -1; // Should never reach here
}

void solutionFree(Solution* obj) {
    free(obj->prefixSum);
    free(obj);
}

using System;

public class Solution {
    private int[] prefixSum;
    private Random rand;

    public Solution(int[] w) {
        prefixSum = new int[w.Length];
        prefixSum[0] = w[0];
        for (int i = 1; i < w.Length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
        rand = new Random();
    }

    public int PickIndex() {
        int totalWeight = prefixSum[prefixSum.Length - 1];
        int target = rand.Next(totalWeight);
        for (int i = 0; i < prefixSum.Length; i++) {
            if (target < prefixSum[i]) {
                return i;
            }
        }
        return -1; // Should never happen
    }
}

Python's 'random' module is utilized to generate a random number. The cumulative weight distribution is maintained in a list, and we go through it linearly to find the appropriate index.

Complexity

Time Complexity: O(N) for initialization, O(N) for each pickIndex call.
Space Complexity: O(N) for list storage of cumulative sums.

Try this approach in the editor

Approach 2: Cumulative Sum with Binary Search

This optimized approach also uses a cumulative sum array, but instead of performing a linear search to find the appropriate index, we use a binary search. This greatly improves the efficiency when determining which index corresponds to a given cumulative value, especially beneficial for larger arrays.

Python

import random
import bisect

class Solution:

    def __init__(self, w):
        self.prefixSum = []
        current_sum = 0
        for weight in w:
            current_sum += weight
            self.prefixSum.append(current_sum)

    def pickIndex(self):
        target = random.randint(0, self.prefixSum[-1] - 1)
        return bisect.bisect_left(self.prefixSum, target + 1)

Java

import java.util.*;

class Solution {
    private int[] prefixSum;
    private Random random;

    public Solution(int[] w) {
        prefixSum = new int[w.length];
        prefixSum[0] = w[0];
        for (int i = 1; i < w.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
        random = new Random();
    }

    public int pickIndex() {
        int totalWeight = prefixSum[prefixSum.length - 1];
        int target = random.nextInt(totalWeight);
        int left = 0, right = prefixSum.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

C++

#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

class Solution {
    vector<int> prefixSum;
public:
    Solution(vector<int>& w) {
        int sum = 0;
        for (int weight : w) {
            sum += weight;
            prefixSum.push_back(sum);
        }
    }
    int pickIndex() {
        int totalWeight = prefixSum.back();
        int target = rand() % totalWeight;
        return lower_bound(prefixSum.begin(), prefixSum.end(), target + 1) - prefixSum.begin();
    }
};

JavaScript

class Solution {
    constructor(w) {
        this.prefixSum = [];
        let sum = 0;
        for (const weight of w) {
            sum += weight;
            this.prefixSum.push(sum);
        }
    }
    pickIndex() {
        const totalWeight = this.prefixSum[this.prefixSum.length - 1];
        const target = Math.floor(Math.random() * totalWeight);
        let left = 0, right = this.prefixSum.length - 1;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (this.prefixSum[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

#include <stdio.h>
#include <stdlib.h>

int compareInts(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

typedef struct {
    int* prefixSum;
    int n;
} Solution;

Solution* solutionCreate(int* w, int wSize) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->prefixSum = (int*)malloc(sizeof(int) * wSize);
    obj->n = wSize;
    obj->prefixSum[0] = w[0];
    for (int i = 1; i < wSize; ++i) {
        obj->prefixSum[i] = obj->prefixSum[i - 1] + w[i];
    }
    return obj;
}

int solutionPickIndex(Solution* obj) {
    int totalWeight = obj->prefixSum[obj->n - 1];
    int target = rand() % totalWeight;
    int left = 0, right = obj->n - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (obj->prefixSum[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

void solutionFree(Solution* obj) {
    free(obj->prefixSum);
    free(obj);
}

using System;

public class Solution {
    private int[] prefixSum;
    private Random random;

    public Solution(int[] w) {
        prefixSum = new int[w.Length];
        prefixSum[0] = w[0];
        for (int i = 1; i < w.Length; i++) {
            prefixSum[i] = prefixSum[i - 1] + w[i];
        }
        random = new Random();
    }

    public int PickIndex() {
        int target = random.Next(prefixSum[prefixSum.Length - 1]);
        int left = 0, right = prefixSum.Length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

The Python solution uses the 'bisect' module to implement a binary search, specifically 'bisect_left', allowing quick location of the correct index to return for a given cumulative target.

Complexity

Time Complexity: O(N) for initialization, O(log N) for each pickIndex call.
Space Complexity: O(N).

Try this approach in the editor

Approach 3: Default Approach

type Solution struct {
	s []int
}

func Constructor(w []int) Solution {
	n := len(w)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i] + w[i]
	}
	return Solution{s}
}

func (this *Solution) PickIndex() int {
	n := len(this.s)
	x := 1 + rand.Intn(this.s[n-1])
	left, right := 1, n-1
	for left < right {
		mid := (left + right) >> 1
		if this.s[mid] >= x {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left - 1
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */

Rust

use rand::{thread_rng, Rng};

struct Solution {
    sum: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl Solution {
    fn new(w: Vec<i32>) -> Self {
        let n = w.len();
        let mut sum = vec![0; n + 1];
        for i in 1..=n {
            sum[i] = sum[i - 1] + w[i - 1];
        }
        Self { sum }
    }

    fn pick_index(&self) -> i32 {
        let x = thread_rng().gen_range(1, self.sum.last().unwrap() + 1);
        let (mut left, mut right) = (1, self.sum.len() - 1);
        while left < right {
            let mid = (left + right) >> 1;
            if self.sum[mid] < x {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        (left - 1) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Cumulative Sum with Linear Search	Time Complexity: O(N) for initialization, O(N) for each pickIndex call. Space Complexity: O(N) for list storage of cumulative sums.
Cumulative Sum with Binary Search	Time Complexity: O(N) for initialization, O(log N) for each pickIndex call. Space Complexity: O(N).
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Cumulative Sum with Linear Search	Init: O(n), Pick: O(n)	O(n)	Simple implementation or when pickIndex is called only a few times
Cumulative Sum with Binary Search	Init: O(n), Pick: O(log n)	O(n)	Best choice when many random picks are required

Frequently asked questions

Is Random Pick with Weight easy or hard?

Random Pick with Weight is generally classified as a medium difficulty problem. The main challenge is recognizing that weighted probability can be converted into prefix sum ranges and then optimized with binary search for repeated queries.

How to solve Random Pick with Weight in O(n)?

Create a prefix sum array where each element represents the cumulative weight up to that index. Generate a random number between 1 and the total weight, then linearly scan the prefix array until the cumulative value is greater than or equal to the random number. Initialization is O(n) and each pick is O(n).

What is the best approach for Random Pick with Weight?

The most efficient approach uses a prefix sum array combined with binary search. Build cumulative weights during initialization, then generate a random number between 1 and the total weight and locate its position using binary search. This gives O(n) preprocessing time and O(log n) time per pick.

What data structure is used in Random Pick with Weight?

The core data structure is a prefix sum array that stores cumulative weights. This array is paired with a random number generator and binary search to efficiently map a random value to the correct weighted index.

What is the time complexity of Random Pick with Weight?

Building the prefix sum array takes O(n) time and O(n) space. Each call to pickIndex() runs in O(log n) using binary search on the prefix array. A simpler linear scan version exists but takes O(n) per pick.

Random Pick with Weight Python or Java solution approach?

Both Python and Java implementations follow the same pattern: build a prefix sum array in the constructor, compute the total weight, generate a random number within that range, and use binary search to locate the index whose prefix sum covers that value.

Is Random Pick with Weight asked at Google, Amazon, or Meta?

Random Pick with Weight appears frequently in interviews focused on probability and prefix sums. Variants of the problem have been reported in Amazon, Google, and Meta interview preparation lists because it tests randomized algorithms and binary search optimization.

Random Pick with Weight solution and explanation

The problem

Approach overview

Approach 1: Cumulative Sum with Linear Search

Approach 2: Cumulative Sum with Binary Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Random Pick with Weight solution and explanation

The problem

Approach overview

Approach 1: Cumulative Sum with Linear Search

Approach 2: Cumulative Sum with Binary Search

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems