Leetcode Problem 380. Insert Delete GetRandom O(1)

380. Insert Delete GetRandom O(1)

Leetcode Solutions

HashMap and ArrayList Approach

  1. Initialize a HashMap and an ArrayList during the construction of the RandomizedSet object.
  2. For insert(val), check if val is already in the HashMap. If it is, return false. Otherwise, add val to the ArrayList and put val and its index into the HashMap, then return true.
  3. For remove(val), check if val is in the HashMap. If it isn't, return false. Otherwise, get the index of val, swap the last element in the ArrayList with val, update the index of the swapped element in the HashMap, remove the last element from the ArrayList, remove val from the HashMap, and return true.
  4. For getRandom(), generate a random index and return the element at that index in the ArrayList.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...