import random
from collections import defaultdict

class Solution:
    # O(1) space and time in initialization. O(n) time and O(1) space when getting the rand index 
    def __init__(self, nums):
        self.nums = nums

    def get_random_index(self, target):
        result, count = None, 0
        for i, num in enumerate(self.nums):
            if num == target:
                if random.randint(0, count) == 0:
                    result = i
                count += 1
        return result

    #Solution 2:
    # O(N) space and time in initilization. O(1) space and time when picking random index
    # def __init__(self, nums):
    #     self.nums = nums
    #     self.mapping = defaultdict(list)
    #     for i, num in enumerate(nums):
    #         self.mapping[num].append(i)
    
    # def get_random_index(self, target):
    #     return random.choice(self.mapping[target])

nums = [1, 3, 2, 2, 3, 3, 3, 4]
solution = Solution(nums)
print(solution.get_random_index(2))
