Random pick index

Hash Table Math Reservoir Sampling Randomized

65.0% acceptance

Jan 12, 2026

1391

1308

Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Implement the Solution class: Solution(int[] nums) Initializes the object with the array nums. int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

struct Solution {
  nums: Vec<i32>,
}

impl Solution {
  fn new(nums: Vec<i32>) -> Self {
    Solution { nums }
  }
  
  fn pick(&self, target: i32) -> i32 {
    use std::collections::hash_map::RandomState;
    use std::hash::{BuildHasher, Hash, Hasher};
    
    let mut result = 0;
    let mut count = 0;
    
    // Reservoir sampling - each matching index has equal probability
    for (i, &num) in self.nums.iter().enumerate() {
      if num == target {
        count += 1;
        
        // Generate random number
        let state = RandomState::new();
        let mut hasher = state.build_hasher();
        (i as u64 + count as u64).hash(&mut hasher);
        let hash = hasher.finish();
        
        // With probability 1/count, pick this index
        if hash % count == 0 {
          result = i as i32;
        }
      }
    }
    
    result
  }
}