Random Pick Index
Medium · Math · Hash Table · Math · Reservoir Sampling · Randomized
Problem
Design a class that, given an integer array that may contain duplicates, returns a uniformly random index of a requested value.
Implement Solution:
- Solution(int[] nums) stores the array.
- int pick(int target) returns an index i with nums[i] == target. When the target occurs several times, each of its indices must be returned with equal probability. The target always occurs in nums.
Because results are random, the examples show one possible outcome. The grader checks that every pick is a valid index and, over long runs, that each index of a target comes up about equally often.
Examples
Input: ops = ["Solution","pick","pick","pick"], args = [[[5,2,5,9,5]],[5],[2],[9]] Output: [None, 2, 1, 3] (one possible outcome)
pick(5) may return 0, 2 or 4, each with chance 1/3; 2 and 9 each occur once, at indices 1 and 3.
Input: ops = ["Solution","pick","pick"], args = [[[7,7]],[7],[7]] Output: [None, 1, 1] (one possible outcome)
Each call independently returns 0 or 1 with chance 1/2.
Constraints
- 1 <= len(nums) <= 2 · 10^4
- -2^31 <= nums[i] <= 2^31 - 1
- target is always present in nums
- At most 10^4 calls are made to pick
Approaches
- Reservoir sampling, O(1) extra memory — time O(n) per pick, space O(1)
Follow-up
The index-list map trades O(n) memory for O(1) picks; reservoir sampling uses O(1) memory and O(n) per pick. The use cases take the randomness out: the first answers "which index is the k-th occurrence", the second replays reservoir sampling with the random numbers given.
Related problems
Start free on Cariara · Coding problems · System design studio
