Minimal Java AC solution with HashMap and PriorityQueue


  • 0
    G

    A simple and straight forward solution using one HashMap and two PriorityQueues.

    class AllOne {
        HashMap<String,Integer> map;
        PriorityQueue<String> minQueue, maxQueue;
        
        /** Initialize your data structure here. */
        public AllOne() {
            map = new HashMap();
            minQueue = new PriorityQueue(new Comparator<String>(){
                @Override
    	        public int compare(String a, String b) {
                    return map.get(a).compareTo(map.get(b));
                }
            });
            maxQueue = new PriorityQueue(new Comparator<String>(){
                @Override
    	        public int compare(String a, String b) {
                    return map.get(b).compareTo(map.get(a));
                }
            });
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            int val = 1;
            if (map.containsKey(key)) {
                val = map.get(key) + 1;
                map.remove(key);
                minQueue.remove(key);
                maxQueue.remove(key);
            }
            map.put(key, val);
            minQueue.add(key);
            maxQueue.add(key);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            int val = 0;
            if (map.containsKey(key)) {
                val = map.get(key) - 1;
                map.remove(key);
                minQueue.remove(key);
                maxQueue.remove(key);
            }
            
            if (val > 0) {
                map.put(key, val);
                minQueue.add(key);
                maxQueue.add(key); 
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            String key = maxQueue.peek();
            return key == null ? "" : key;
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            String key = minQueue.peek();
            return key == null ? "" : key;        
        }
    }
    

Log in to reply
 

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