Logic behind using a hashmap and an arraylist.


  • 1
    B

    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.


  • 0
    G

    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?


Log in to reply
 

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