Random Pick Index

Problem Description

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.

Key Insights

• The solution needs to handle duplicate elements in the array.
• Each index where the target appears should have an equal probability of being returned.
• A straightforward approach could involve iterating through the array and collecting indices of the target.

Space and Time Complexity

Time Complexity: O(n) for the initialization, where n is the length of the array. Each pick operation takes O(k), where k is the number of occurrences of the target. Space Complexity: O(n) for storing the indices of the target elements.

Solution

To solve this problem, we can use a list to store all the indices of the target elements during the initialization of the Solution class. When the pick method is called, we can randomly select an index from this list of indices. This approach ensures that each index is chosen with equal probability.

1. Use a list to store the indices of the target in the nums array.
2. Use a random number generator to select one of these indices.

Code Solutions