# Random Pick Index

````cpp
// https://leetcode.com/problems/random-pick-index/

/*
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.

Ex1:

Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]

Explanation
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
*/

#include <vector>
#include <unordered_map>

using namespace std;

class IndexPicker {
public:
    vector<int> nums;
    unordered_map<int, vector<int>> m;
    IndexPicker(vector<int>& nums) : nums(nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (!m.count(nums[i])) {
                m[nums[i]] = {i};
            } else {
                m[nums[i]].push_back(i);
            }
        }
    }

    int pick(int num) {
        if (!m.count(num)) {
            return -1;
        }

        vector<int> indices = m[num];
        int n = indices.size();
        int idx = rand() % n;
        return indices[idx];
    }

};

// Reservoir Sampling
// Shuffle an array
// Linked List Random Node.
class Solution {
public:

    vector<int> nums;

    Solution(vector<int>& nums) {
        this->nums.swap(nums);
    }

    int pick(int target) {
        int n = nums.size();
        int count = 0;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            // if nums[i] is equal to target, i is a potential candidate
            // which needs to be chosen uniformly at random
            if (nums[i] == target) {
                // increment the count of total candidates
                // available to be chosen uniformly at random
                count++;
                // we pick the current number with probability 1 / count (reservoir sampling)
                if (rand() % count == 0) {
                    idx = i;
                }
            }
        }
        return idx;
    }
};```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dongzeli95s-organization.gitbook.io/swe-interview-handbook/algorithm/random/random_pick_index.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.