### View *Random Pick Index* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(n) - The program must initialize the hash table with the user input, resulting in the O(n) time complexity.

**Space Complexity**

O(n) - The program must store each of the user’s input numbers, resulting in the O(n) space complexity.

**Runtime Beats**

95.45% of other submissions

**Memory Beats**

85.52% of other sumbissions

## Explanation

To decrease the time complexity of each call of the method `pick`

the program initializes a dictionary of `target : [indices]`

pairs. This allows for quick access to the indices where `target`

only leaivng a random selection of an index, which is an O(1) operation, making `pick`

take O(1).

## Data Structure Used

**Hash Table (Set) -** An unordered container of non-repeating values.

**Visual Examples**

An array being transformed into a set, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = {}
# Populate the nums dict with (num : [indices]) pairs
for i,n in enumerate(nums):
if n not in self.nums:
self.nums[n] = [i]
else:
self.nums[n].append(i)
def pick(self, target: int) -> int:
# Choice a random index out of the retrieved indices for the target number
return random.choice(self.nums[target])