SImple Java HashMap Solution -- time complexity


  • 0
    M

    what is the time and space complexity of this code in worse cases.

    class MapSum {
    
        /** Initialize your data structure here. */
        Map<String, Integer> myMap;
        int sum ;
        
        public MapSum() {
            myMap = new HashMap<String,Integer>();
            sum = 0;
        }
        
        public void insert(String key, int val) {
            myMap.put(key,val);
        }
        
        public int sum(String prefix) {
            sum = 0;
          for(String key: myMap.keySet()) {
              
                if(key.startsWith(prefix)) {
            
                    sum +=  myMap.get(key);
                }
          
            }
            return sum;
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */
    

  • 0
    C

    O(keys * averageKeyLength) per query

    You can improve to O(averageKeyLength) by using a trie instead of a HashMap


Log in to reply
 

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