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])