Readable Java HashMap+ArrayList Solution


  • 0

    Basically we reuse the code structure of problem Insert Delete GetRandom O(1). The only change is to extend original HashMap<val,idx> to HashMap<val,<idx1,idx2...>>. While it takes some time for to decide which data structure to be used as the value of HashMap. At first I thought Queue or Stack, but at last I found the problem: it's convenient to remove element from head, but it cannot remove any index in O(1), which is required when we copy the last element of ArrayList to overwrite deleted one. Finally, I decided to use HashSet inside the map. Here is my solution for your reference.

        private Random rand = new Random();
        private List<Integer> list = new ArrayList<>();
        private Map<Integer,Set<Integer>> bag = new HashMap<>();
        
        public boolean insert(int val) {
            boolean isNew = false;
            if (!bag.containsKey(val)) {
                bag.put(val, new HashSet<>());
                isNew = true;
            }
            bag.get(val).add(list.size());
            list.add(val);
            return isNew;
        }
        
        public boolean remove(int val) {
            if (bag.containsKey(val)) {
                int idx = bag.get(val).iterator().next();
                bag.get(val).remove(idx);
                // Copy last one to deleted position
                if (idx < list.size() - 1) {
                    int lastval = list.get(list.size() - 1);
                    bag.get(lastval).remove(list.size() - 1);
                    bag.get(lastval).add(idx);
                    list.set(idx, lastval);
                }
                // Delete last one
                list.remove(list.size() - 1);
                if (bag.get(val).isEmpty()) {
                    bag.remove(val);
                }
                return true;
            }
            return false;
        }
        
        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.