Java AC solution with single HashMap - O(1) solution, beats 93%


  • 0
    G

    This Solution is with one single HashMap and using get and put operation. So this O(1) solution using single HashMap.

    class AllOne {
    
        Map<String, Integer> map;
        /** Initialize your data structure here. */
        public AllOne() {
            map = new HashMap<String, Integer>();
        }
        
        /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
        public void inc(String key) {
            if(!map.containsKey(key))
                map.put(key, 0);
                
            map.put(key, map.get(key) + 1);
        }
        
        /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
        public void dec(String key) {
            if(map.containsKey(key))
            {
                if(map.get(key) == 1)
                    map.remove(key);
                else
                    map.put(key, map.get(key) - 1);
            }
        }
        
        /** Returns one of the keys with maximal value. */
        public String getMaxKey() {
            int max = Integer.MIN_VALUE;
            String val = "";
            for(String key : map.keySet())
            {
                int temp = max;
                max = Math.max(max, map.get(key));
                
                if(max > temp)
                    val = key;
            }
            
            if(max == Integer.MIN_VALUE)
                return "";
            else
                return val;
        }
        
        /** Returns one of the keys with Minimal value. */
        public String getMinKey() {
            int min = Integer.MAX_VALUE;
            String val = "";
            for(String key : map.keySet())
            {
                int temp = min;
                min = Math.min(min, map.get(key));
                
                if(min < temp)
                    val = key; 
            }
            
            if(min == Integer.MAX_VALUE)
                return "";
            else
                return val;
        }
    }
    

Log in to reply
 

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