Practice/Meta/Leetcode 398. Random Pick Index

Leetcode 398. Random Pick Index

CodingMust

Problem

Design a class that stores an integer array (which may contain duplicate values) and provides a method to retrieve a random index where a specific target value appears. When the target value exists at multiple positions in the array, each valid index must have an equal probability of being selected.

Your class should implement:

• A constructor that accepts the array
• A pick(target) method that returns a uniformly random index i where nums[i] == target

Requirements

1. The constructor receives an array of integers that may contain duplicates
2. The pick(target) method must return a valid index where the target value exists
3. If multiple indices contain the target value, each must be selected with equal probability
4. The solution should efficiently handle multiple calls to pick()
5. You may assume the target value always exists in the array

Constraints

• 1 ≤ nums.length ≤ 20,000
• -2³¹ ≤ nums[i] ≤ 2³¹ - 1
• target is guaranteed to be in nums
• At most 10,000 calls will be made to pick

Examples

Example 1:

` Input: nums = [1, 2, 3, 3, 3] Operations: pick(3) → could return 2, 3, or 4 (each with ~33% probability) pick(1) → returns 0 pick(3) → could return 2, 3, or 4 (each with ~33% probability)

Explanation:

• The value 3 appears at indices 2, 3, and 4
• Each call to pick(3) should randomly select one of these indices with equal probability
• The value 1 only appears at index 0, so pick(1) always returns 0 `

Example 2:

` Input: nums = [4, 4, 4, 4] Operations: pick(4) → could return 0, 1, 2, or 3 (each with 25% probability)

Explanation:

• All elements are 4, so any index should be equally likely `