Random Pick Index - Leetcode Solution

Problem Statement:

Given an array of integers 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.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
solution.pick(3); // will return either 2, 3, or 4 randomly

Solution: To solve this problem, we need to pick a random index i with the property that nums[i] == target. There are several approaches to solving this problem but we will discuss two of them.

Approach 1:

The first approach is to use the reservoir sampling algorithm. The algorithm is as follows:

1. Initialize a variable called count to hold the number of occurrences of the target element in the array.
2. Initialize a variable called index to hold the index of the target element.
3. Initialize a variable called i to hold the value 0.
4. Iterate over the array and for each element nums[j]:
    a. If nums[j] == target:
        i. Increment count by 1.
        ii. With a probability of 1/count, update index to j (replace the previous value of index).
5. Return the value of index.

The time complexity of this algorithm is O(n), where n is the size of the input array.

import random
import time

class Solution:

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

    def pick(self, target: int) -> int:
        count = 0
        index = -1
        for i, num in enumerate(self.nums):
            if num == target:
                count += 1
                if random.randint(1, count) == 1:
                    index = i
        return index

Approach 2:

Alternatively, we can solve this problem using Hash Map. The idea is to first create a hash map that maps the target elements to their corresponding indices in the input array. Then we can randomly select an index from the list of indices corresponding to the given target element.

The time complexity of this approach is O(n) to build the hash map, and the time complexity of the pick() function is O(1).

import random
import time
from collections import defaultdict

class Solution:

    def __init__(self, nums: List[int]):
        self.indices = defaultdict(list)
        for i, num in enumerate(nums):
            self.indices[num].append(i)

    def pick(self, target: int) -> int:
        return random.choice(self.indices[target])

1