algoadvance

You need to implement the Solution class which has a method pick that randomly picks an index of a given target number from an integer array.

• Implement the Solution class:
  • Solution(int[] nums) Initializes the object with the array nums.
  • int pick(int target) Picks a random index from nums where nums[index] == target. If there are multiple valid indices, each index should have an equal probability of being returned.

Example

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);     // Returns index 2, 3, or 4 randomly.
solution.pick(1);     // Returns index 0.
solution.pick(3);     // Returns index 2, 3, or 4 randomly.

Note that any index with nums[index] == target should be returned with equal probability.

Clarifying Questions

1. Input Constraints: What are the constraints on the size and values of the input array?
   • Answer: The array nums will have a length between 1 and 10^4. Each element will be an integer within the range [−10^7, 10^7].
2. Target Occurrence: Can the target occur multiple times, or can it be absent in nums?
   • Answer: The target can occur multiple times. It won’t be guaranteed that the target is always present.

Strategy

1. Class Initialization (__init__ method):
   • Store the input list nums.
2. Random Index Picking (pick method):
   • Traverse the stored nums array to collect all indices where the element equals the target.
   • Randomly select one index from the collected list of valid indices.

For randomness, Python’s random module, specifically the random.choice method, will be useful for selecting a random index from the list of valid indices.

Time Complexity

• Initialization: O(n) where n is the length of nums.
• Pick Method: O(n) in the worst case, where we traverse the entire array when there is no early termination condition.

Here’s the implementation:

import random

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums
    
    def pick(self, target: int) -> int:
        # Collect all indices where nums[index] == target
        valid_indices = [i for i, num in enumerate(self.nums) if num == target]
        # Randomly pick one of these indices
        return random.choice(valid_indices)

The above solution should implement the requirements efficiently and correctly, leveraging list comprehension and random choice for simplicity and performance.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?