No nested Set; only HashMap<Integer, Integer> and ArrayList<Node> (beats 97%)


  • 0
    A

    The idea is the same as in the task without duplicates: HashMap maps a value to the index in the ArrayList. The latter consists of Node, which holds (value, index in the array and reference to the previously added Node with the same value). The main trick is that Nodes with the same values are organized in the linked list. HashMap points to the index of the head.

    Non-duplicate values are handled as in the task without duplicates. When duplicate value is added, the new Node is created with the link to the previous Node with the same value, and HashMap is updated with the index of the new Node.

    Deletion is a bit tricky. One needs to update the index of the Node and (value, index) pair of the map, if the head of duplicates is moved. If duplicate is removed, the (value, index) pair must be updated with the index of the previous duplicate.

    public class RandomizedCollection {
        
        class Node {
            int val;
            Node prev;
            int index;
            public Node(int val, int index, Node prev) {
                this.val = val;
                this.prev = prev;
                this.index = index;
            }
        }
        
        ArrayList<Node> array = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        Random rand = new java.util.Random(System.nanoTime());
    
        public RandomizedCollection() {
            
        }
        
        public boolean insert(int val) {
            if (map.containsKey(val)) {
                Node prev = array.get(map.get(val));
                int newIndex = array.size();
                array.add(new Node(val, newIndex, prev));
                map.put(val, newIndex);
                return false;
            }
            int index = array.size();
            array.add(new Node(val, index, null));
            map.put(val, index);
            return true;
        }
    
        public boolean remove(int val) {
            Integer index = map.get(val);
            if (index == null) return false;
            Node node = array.get(index);
            if (node.prev == null) map.remove(val);
            if (index == array.size() - 1) {
                if (node.prev != null) map.put(val, node.prev.index);
                array.remove(array.size() - 1);
                return true;
            }
            Node relocated = array.get(array.size() - 1);
            if (map.get(relocated.val) == relocated.index) map.put(relocated.val, index);
            relocated.index = index;
            array.set(index, relocated);
            array.remove(array.size() - 1);
            if (node.prev != null) map.put(val, node.prev.index);
            return true;
        }
        
        public int getRandom() {
            return array.get(rand.nextInt(array.size())).val;
        }
    }
    

Log in to reply
 

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