# Logic behind using a hashmap and an arraylist.

• If we just use a hashset (unordered_set), then we can implement both `insert()` and `remove()` in O(1) time, by using the `insert()` and `erase()` methods. [Refer this link for more details].

The only challenge is with implementing `getRandom()` in `O(1)`. Something naive like just `rand()` cannot be used on a hashset, so we need to use the `std::advance()` method which would inturn result in this being an `O(n)` method.

Thus, in order to implement `getRandom()` as well in O(1), we need to use a different method (of using a hashMap and arraylist) than just using a hashset.

Please let me know if you find something incorrect in this post.

Thanks,
BatCoder.

• I was able to get an accepted submission by converting the HashSet to an Integer array, then acquiring a random value from the array. It was a slower time than most other submissions, but it still worked.

``````public int getRandom() {
Integer[] arr = new Integer[set.size()];
set.toArray(arr);
Random rand = new Random();
return arr[rand.nextInt(set.size())];
}
``````

Behind the scenes, what's the O converting a HashSet to array?

• @GreyHaven I don't think your `getRandom()` is `O(1)`, since you are converting the HashSet to an integer array. When doing this, you visit all the elements in the HashSet and so your time complexity becomes `O(n)`. As for getting accepted, well, that is because you are using Java - although slower (than C++) it is still pretty fast than Python. I am pretty sure your solution in Python won't pass (assuming the timings on the judge have been fine tuned).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.