Leetcode Problem 381. Insert Delete GetRandom O(1) - Duplicates allowed

381. Insert Delete GetRandom O(1) - Duplicates allowed

Leetcode Solutions

ArrayList and HashMap for O() Operations

  1. Initialize an ArrayList and a HashMap.
  2. For insert(val), add val to the ArrayList and add the index to the set of indices in the HashMap corresponding to val. Return true if the set was previously empty, false otherwise.
  3. For remove(val), if val is not in the HashMap, return false. Otherwise, get an index of val from the set, swap the element at this index with the last element in the ArrayList, update the HashMap for the swapped element, remove the last element from the ArrayList, and remove the index from the set in the HashMap. Return true.
  4. For getRandom(), return an element from the ArrayList at a random index.
UML Thumbnail

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...