Accepted with Latest testcases: Java soln using HashMap, Deque, ArrayList


  • 0
    R
      // Using a double ended queue(Deque) to keep track of the indices for the duplicate elements
        List<Integer> list;
        Map<Integer, Deque<Integer>> map;
        Random rand = new Random();
    
        /** 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 contain = map.containsKey(val);
            if(!contain) map.put(val, new ArrayDeque<>());
            list.add(val);
            map.get(val).addLast(list.size()-1);
            return !contain;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val)) return false;
            int loc = map.get(val).peekLast();
            map.get(val).removeLast();
            if(loc < (list.size()-1)){
                int lastKey = list.get(list.size()-1);
                list.set(loc, lastKey);
                // removing from the last and adding in the front so that we don't keep changing index for the same element
                map.get(lastKey).removeLast();
                map.get(lastKey).addFirst(loc);
            }
            list.remove(list.size()-1);
            if(map.get(val).isEmpty()) map.remove(val);
            return true;
        }
    
        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get(rand.nextInt(list.size()));
        }
    

Log in to reply
 

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