DIY: Random Pick Index

Problem statement

In this challenge, you are given an array of integers with possible duplicate values. Your task is to output a randomly picked index of a given target number present in the array. The solution should be memory efficient even if the array is very large. Additionally, you can assume that the given target number always exists in the array.

Input

The Solution module’s init function will take an array of integers called nums as input. Whereas, the module’s pick() function will take the integer value target as input along with the struct object, obj. The following is an example of the inputs:

nums = [1,2,2,3,3,3,4]
target = 3

Output

The pick() function’s output will be an integer representing a randomly selected index of the target value in the nums array. The following is a possible output for the inputs given above:

4