Simple Java HashMap Solution - O(1) sum, and O(len(key)) insert


  • 7

    UPDATE : Okay, let me tell you that even though solution look so concise, why you should NOT do this.
    It's because of s += c. This operation is not O(1), it's O(String::length), which makes for loop to be k^2. And this will break when string is long. Try it yourself as learning with this input for insert - https://pastebin.com/Pjymymgh

    But if the constraint is that the string are small, like dictionary words or people names, then it should be good.

    The key idea is to keep two hash maps, one with just original strings. The other with all prefixes.

    When a duplicate insert is found, then update all it's prefixes with the difference of previous value of the same key(take it from original map)

    Time Complexity for sum is O(1)
    Time Complexity for insert is O(len(key)) O(len(key) ^ 2)

    /** Initialize your data structure here. */
    Map<String, Integer> map;
    Map<String, Integer> original;
    public MapSum() {
        map = new HashMap<>();
        original = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        val -= original.getOrDefault(key, 0); // calculate the diff to be added to prefixes
        String s = "";
        for(char c : key.toCharArray()) {
            s += c; // creating all prefixes
            map.put(s, map.getOrDefault(s, 0) + val); //update/insert all prefixes with new value
        }
        original.put(key, original.getOrDefault(key, 0) + val);
    }
    
    public int sum(String prefix) {
        return map.getOrDefault(prefix, 0);
    }

  • 0

    Here I use val -= original.getOrDefault(key, 0) to get the difference to be updated among all exisiting prefixes with new val.

    Why I have to keep original map as well because I add prefixes to the map, and sum call should be able to differentiate b/w prefixes and original. Also if apple is a prefix of the next call, I should still preserve the value of apple in original map.


  • 0
    C

    My method is to check all available prefix in the map, so O(1) for insert, O(n) for sum:

    class MapSum {
    
        private Map<String, Integer> map;
        
        public MapSum() {
            map = new HashMap<>();    
        }
        
        public void insert(String key, int val) {
            map.put(key, val);
        }
        
        public int sum(String prefix) {
            
            int count = 0;
            
            for (String key : map.keySet()) {
                
                String keyPrefix = prefix.length() > key.length() ? key : key.substring(0, prefix.length());
                if (keyPrefix.equals(prefix))
                    count += map.getOrDefault(key, 0);
            }
            
            return count;
        }
    }
    

  • 0

    @CHYGO said in Simple Java HashMap Solution - O(1) sum, and O(len(key)) insert:

    I think you do not need to do this, simple use map.put(s, val);
    if s already exists in the map, the map will replace the old value with val.

    thanks for comment but That is not right. I need to compute the difference to replace the value.
    Lets say if apple is value 10. New value is 7. I need to add -3 to all the prefixes that were created before. You can't just replace 7.

    And your method is going through all the keys, so our solutions are totally different.


  • 1
    C

    @wavy I see, I see, I did not check your solution very carefully, thank you for pointing out :) have already edited my post.


  • 0
    T

    Great solution! But using two map should take more space, right?


  • 0

    @wavy Thank you for your code. But I am not sure if we need two maps. I used a single one and I think it is correct:

    class MapSum {
    public:
        /** Initialize your data structure here. */
        unordered_map<string, int> hashMap;
        MapSum() {
            hashMap.clear();
        }
        
        void insert(string key, int val) {
            hashMap[key]=val;
        }
        
        int sum(string prefix) {
            unordered_map<string, int>::iterator it;
            it=hashMap.begin();
            int sum=0;
            
            while(it!=hashMap.end()) {
                if((it->first).find(prefix)==0)
                    sum+=it->second;
                it++;
            }
            
            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);
     */
    

    Since the question says that the string in the map must start with the prefix, I just check if the start position of the prefix in the map key (string) is 0.


  • 0

    @BatCoder said in Simple Java HashMap Solution - O(1) sum, and O(len(key)) insert:

    But I am not sure if we need two maps. I used a single one and I think it is correct:

    Thanks for suggestion. But that is not right. I have said previous that we need two maps to keep track of original scores. Your solution and my solution are different. Please go through my solution again.


  • 1
    H
    s += c;
    

    if use StringBuilder can reduce O(len(key) ^ 2) ?


  • 1

    @kangbin2356 No, because I still have to create a string out of it, so if I use a string builder, I still have to do stringbuilder.toString() in every loop.


  • 0
    C
    This post is deleted!

  • 0
    H

    @CHYGO This same was my implementation that day.. but it wasnt working for me.. were you able to successfully submit this solution that day or just suggesting now?


  • 1
    A

    Your solution is good. This can be done by 1 HashMap as well. insert - O(1), sum O(n)

    Map<String, Integer> map;
    /** Initialize your data structure here. */
    public MapSum() {
        map = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        map.put(key, val);
    }
    
    public int sum(String prefix) {
        int sum = 0;
        for (String s: map.keySet()) {
            if (s.startsWith(prefix)) {
                sum += map.get(s);
            }
        }
        return sum;
    }

  • 0
    C

    @hprem991 Sure thing, I won't post code that does not work :)


  • 0
    W
    This post is deleted!

  • 0
    F
    class MapSum {
    
        HashMap<String, Integer> map;
        /** Initialize your data structure here. */
        public MapSum() {
            map = new HashMap<>();
        }
        
        public void insert(String key, int val) {
            map.put(key, val);
        }
        
        public int sum(String prefix) {
            int sum = 0;
            for (Map.Entry<String, Integer> entry: map.entrySet()) {
                if (entry.getKey().startsWith(prefix)) {
                    sum += entry.getValue();
                }
            }
            return sum;
        }
    }
    

  • 0
    I

    I feel like even you can do it in O(len(key)). The biggest problem of this solution is you need so much memory to store all the prefixes.


Log in to reply
 

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