Random Pick Index

Problem statement

You’re given an integer array that may contain duplicates. Implement a class that, given a target, returns a uniformly random index i where nums[i] == target. Each matching index should have the same probability.

Example:

Input:

nums = [1, 2, 3, 3, 3]
Pick(3)  // each of indices 2, 3, 4 equally likely

Practice on LeetCode: Random Pick Index

Golang Solution

One-pass reservoir sampling: walk the array, keep a running count of how many times target has appeared, and with probability 1/count replace the chosen index. That keeps every match equally likely without storing the full index list.

Time: O(n) per Pick
Space: O(1) extra beyond storing nums

type Solution struct {
	nums []int
}

func Constructor(nums []int) Solution {
	return Solution{
		nums: nums,
	}
}

func (s *Solution) Pick(target int) int {
	count := 0
	result := -1

	for i, num := range s.nums {
		if num != target {
			continue
		}

		count++

		if rand.Intn(count) == 0 {
			result = i
		}
	}

	return result
}