How do you solve Random Pick with Weight on LeetCode?

Random Pick with Weight (LeetCode #528) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(n) space complexity. Key insight: Using a prefix sum allows for efficient random selection based on weights.

What is the brute force solution for Random Pick with Weight?

The brute force approach for Random Pick with Weight is Brute Force, with O(n) time complexity and O(1) space complexity. In the brute force approach, we can simulate the random picking by generating a random number and checking which index it corresponds to based on the weights. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(log n).

What are the interview tips for Random Pick with Weight?

Explain your thought process clearly while coding. Discuss the trade-offs of different approaches. Practice implementing binary search as it's a common pattern.

What are common mistakes when solving Random Pick with Weight?

Not considering the range of random numbers correctly. Confusing the prefix sum with cumulative weights.

#528

Random Pick with Weight

Medium

ArrayMathBinary SearchPrefix SumRandomizedHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log n)
Space	O(1)	O(n)

💡

Intuition

Time O(log n)Space O(n)

The optimal solution uses a prefix sum array to efficiently determine the index based on the weights. This allows us to use binary search, making the picking process faster.

⚙️

Algorithm

3 steps

1Step 1: Create a prefix sum array where each element at index i is the sum of weights from index 0 to i.
2Step 2: Generate a random number between 1 and the total sum of weights.
3Step 3: Use binary search to find the first index in the prefix sum array that is greater than or equal to the random number.

solution.py12 lines

1# Full working Python code
2import random
3import bisect
4class Solution:
5    def __init__(self, w):
6        self.prefix_sum = [0] * len(w)
7        self.prefix_sum[0] = w[0]
8        for i in range(1, len(w)):
9            self.prefix_sum[i] = self.prefix_sum[i-1] + w[i]
10    def pickIndex(self):
11        target = random.randint(1, self.prefix_sum[-1])
12        return bisect.bisect_left(self.prefix_sum, target)

ℹ

Complexity note: The time complexity is O(log n) due to the binary search on the prefix sum array. The space complexity is O(n) because we store the prefix sums.

1Using a prefix sum allows for efficient random selection based on weights.
2Binary search optimizes the index selection process.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.