Few Changes From GetRandom O(1) -- ArrayList && HashMap Solution

  • 0

    Based on the solution from the LC380, I come up with this solution with some helpful comments...

    public class RandomizedCollection {
        List<Integer> list; //store number
        Map<Integer, Set<Integer>> map; // <Number, Position>
        /** Initialize your data structure here. */
        public RandomizedCollection() {
            list = new ArrayList<>();
            map = new HashMap<>();
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            boolean isContain = map.containsKey(val);
                map.put(val, new HashSet<>());
            return !isContain;
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
                return false;
            if(!map.get(val).contains(list.size() - 1)) {
                //get the location of the element
                int location = map.get(val).iterator().next();
                //remove the location in the set
                //get the last element in the list
                int last = list.get(list.size() - 1);
                //set the last element in the location
                list.set(location, last);
                //update the location of the last element
                map.get(last).remove(list.size() - 1);
                map.get(val).remove(list.size() - 1);
            //if empty set, remove the key-value pair from the map
            //remove the last element in the list
            list.remove(list.size() - 1);
            return true;
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get((int)(Math.random() * list.size()));
     * Your RandomizedCollection object will be instantiated and called as such:
     * RandomizedCollection obj = new RandomizedCollection();
     * boolean param_1 = obj.insert(val);
     * boolean param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();

    Hope that will help.

Log in to reply

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