Logic behind using a hashmap and an arraylist.

  • 2

    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.


  • 0

    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()];
    	Random rand = new Random();
    	return arr[rand.nextInt(set.size())];

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

  • 0

    @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).

Log in to reply

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