329/670

329. Random Pick Index

Medium

Design a class over an integer array nums that may contain duplicates:

Solution(nums) — receives the array once and builds whatever structure you need.
pick(target) — returns an index i such that nums[i] == target. Every queried target is guaranteed to exist in nums.

In the interview version of this problem, pick must return a uniformly random index among all positions holding target (reservoir sampling is the famous answer — the editorial covers it). Because this judge compares output exactly, we pin a deterministic rule instead: repeated calls with the same target cycle through its occurrence indices in increasing order — the first call returns the smallest such index, the second the next-smallest, and after the largest it wraps back around to the smallest. Each distinct target keeps its own independent cycle.

Example 1:

Input: nums = [1, 2, 3, 3, 3], picks = [3, 1, 3, 3, 3]

Output: [2, 0, 3, 4, 2]

Explanation: The value 3 lives at indices 2, 3 and 4. Successive picks of 3 walk that list in order and wrap: 2, then 3, then 4, then back to 2. The single pick of 1 returns its only index, 0.

Example 2:

Input: nums = [7, 7, 7], picks = [7, 7, 7, 7]

Output: [0, 1, 2, 0]

Explanation: Every element equals 7, so picks cycle through indices 0, 1, 2 and then wrap to 0 on the fourth call.

Constraints:

1 ≤ nums.length ≤ 2 * 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
Every target passed to pick occurs at least once in nums.
At most 10⁴ calls will be made to pick.

Hints:

Where does each value live? One pass over nums can build a hash map from value to the list of its indices (already in increasing order, since you append as you scan).

Keep a second map counting how many times each target has been picked so far; the c-th call (0-based) for a target with m occurrences returns occurrences[c % m]. For the true random variant, read up on reservoir sampling: scan the occurrences and replace your current choice of the c-th match with probability 1/c.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: nums = [1, 2, 3, 3, 3], picks = [3, 1, 3, 3, 3]

Expected output: [2, 0, 3, 4, 2]