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.

For example:

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.

How would you implement this Solution class to efficiently handle the pick operation, ensuring each valid index has an equal probability of being returned? What are the time and space complexity of your solution?

import random

class Solution:

    def __init__(self, nums: list[int]):
        self.nums = nums

    def pick(self, target: int) -> int:
        indices = [i for i, num in enumerate(self.nums) if num == target]
        return random.choice(indices)


# Your Solution object will be instantiated and called as such:
# nums = [1, 2, 3, 3, 3]
# obj = Solution(nums)
# param_1 = obj.pick(3)
# print(param_1)

Brute Force Solution

The provided solution is a brute-force approach to solve the problem. It iterates through the entire array to identify all indices where the element matches the target, and then randomly selects one of these indices. This is straightforward and easy to understand.

Optimal Solution

The provided solution is reasonably optimal for this problem, especially considering the constraints (at most 10^4 calls to pick). More advanced techniques (like using a hash map to pre-compute indices) might offer marginal improvements, but the overhead of building the hash map could negate the benefits if pick is called infrequently.

Big(O) Run-Time Analysis

The __init__ method takes O(1) time because it simply stores a reference to the input array.

The pick method has a time complexity of O(n), where n is the length of the nums array. This is because, in the worst-case scenario (e.g., when every element in the array equals the target), it has to iterate through the entire array to find all indices that match the target value.

Big(O) Space Usage Analysis

The __init__ method takes O(1) space, as it only stores a reference to the input array, not making a copy.

The pick method takes O(k) space, where k is the number of occurrences of the target value in the array. In the worst-case scenario, where every element in the array is equal to the target value, k would be equal to n, and the space complexity would be O(n).

Edge Cases

1. Empty Array: If the input array is empty, the code will still run but the pick method will fail if called, because there will be no target to pick. This is avoided by the constraint that 1 <= nums.length.
2. Target Not Found: The problem states that the target is guaranteed to be in the array. If the target were not in the array, the indices list in pick would be empty, causing random.choice to throw an error. This scenario is prevented by the problem statement.
3. Large Array, Many Targets: If the array is very large and contains many instances of the target element, the space complexity of pick could become a concern (O(n) in the worst case). However, given the constraints, this is unlikely to be a significant issue.