Arrays & Hashing
LC #380Medium
Insert Delete GetRandom O(1)
Arrays & Hashing
Problem
Implement the RandomizedSet class with O(1) average time complexity for insert, remove, and getRandom.
arrayhash-mapdesign
Constraints
- ›-2³¹ ≤ val ≤ 2³¹ - 1
- ›At most 2 * 10⁵ calls total to insert, remove, and getRandom
- ›There will be at least one element when getRandom is called.
Example
Input
insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()Output
true, false, true, 1 or 2, true, false, 2Why
getRandom returns either 1 or 2 with equal probability initially.