🎨Now live: Try our Free AI Image Generation Feature

Description
Given an array of integers, we need to pick an index at random from the array where a given target number appears. The key challenge is to ensure each target number is picked with equal probability, even when the target appears multiple times in the array.
Intuition
To ensure equal probability of picking any occurrence of the target, we can use a reservoir sampling technique. As we iterate over the array and encounter each instance of the target, we randomly decide whether to select this index, progressively reducing the likelihood as more instances are encountered.
Approach
- Initialize a result
res
as -1 and acount
to keep track of how many times the target has been seen. - Loop through the array:
- Each time the target is found, increase the count and pick the current index with probability
1/count
. - Use randomization to decide whether to updateres
to the current index. - Return the chosen index after iterating through the array.
Complexity
Time Complexity:
O(n)
, where n
is the number of elements in the array.
Space Complexity:
O(1)
, excluding the input array, as only a few extra variables are used.
Code
C++
class Solution {
public:
vector nums;
Solution(vector& nums) {
this->nums = nums;
}
int pick(int target) {
int res = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
count++;
if (rand() % count == 0) {
res = i;
}
}
}
return res;
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(nums);
* int param_1 = obj->pick(target);
*/
Python
class Solution:
def __init__(self, nums: list[int]):
self.nums = nums
def pick(self, target: int) -> int:
res = -1
count = 0
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(0, count - 1) == 0:
res = i
return res
Java
class Solution {
private int[] nums;
private Random random;
public Solution(int[] nums) {
this.nums = nums;
this.random = new Random();
}
public int pick(int target) {
int res = -1;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
count++;
if (random.nextInt(count) == 0) {
res = i;
}
}
}
return res;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int param_1 = obj.pick(target);
*/
JavaScript
var Solution = function(nums) {
this.num = nums;
};
/**
* @param {number} target
* @return {number}
*/
Solution.prototype.pick = function(target) {
let res = -1, count = 0;
for(let i = 0; i < this.num.length; i++) {
if(this.num[i] === target) {
count++;
if(Math.floor(Math.random() * count) === 0) {
res = i;
}
}
}
return res;
};