Logic behind using a hashmap and an arraylist.

  • 0

    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.


Log in to reply

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