Map Sum Pairs - Leetcode Solution

Problem Statement:

Implement the MapSum class:

MapSum() Initializes the MapSum object. void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one. int sum(String prefix) Returns the sum of all the pairs' value whose key starts with the prefix.

Example:

Input: ["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output: [null, null, 3, null, 5]

Explanation: MapSum mapSum = new MapSum(); mapSum.insert("apple", 3); mapSum.sum("ap"); // return 3 (apple = 3) mapSum.insert("app", 2); mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)

Solution:

We can solve this problem using Trie data structure. Trie is a tree-like data structure that stores a collection of strings. Each node holds a character and there is a root node at the top of the tree. The children of a node are the characters that follow the current node’s character.

Let's implement the logic of Trie,

class TrieNode { public Map<Character, TrieNode> children; public int value;

public TrieNode() {
    children = new HashMap<>();
    value = 0;
}

}

In MapSum class, we can implement insert method as below,

public void insert(String key, int val) { TrieNode node = root; for(char c : key.toCharArray()) { if(node.children.get(c) == null) { node.children.put(c, new TrieNode()); } node = node.children.get(c); } node.value = val; map.put(key, val); }

In the above method, we are traversing through each character of the key, and if a character is not present in the children of the current node, we are creating a new TrieNode for that character. We are then moving the pointer to the new node as we move forward in the key. Finally, we are storing the value in the last TrieNode.

Now, let's implement the sum method to get the desired output.

public int sum(String prefix) { if(prefix == null || prefix.isEmpty()) { return 0; } TrieNode node = root; for(char c : prefix.toCharArray()) { if(node.children.get(c) == null) { return 0; } node = node.children.get(c); } return dfs(node); }

In the above method, we are traversing through each character of the prefix in the same way as we did in the insert method. If a character is not present in the children of the current node, we are returning 0. Once we reach the last node of prefix, we are calling a dfs helper method that computes the sum of all values present in the TrieNodes below it.

private int dfs(TrieNode node) { int sum = node.value; for(char c : node.children.keySet()) { sum += dfs(node.children.get(c)); } return sum; }

In the above helper method, we are recursively traversing through all the children of the TrieNode and adding up their values in the sum variable.

Finally, let's create a MapSum class which will use the above-defined methods,

class MapSum { private TrieNode root; private Map<String, Integer> map;

public MapSum() {
    root = new TrieNode();
    map = new HashMap<>();
}

public void insert(String key, int val) {
    TrieNode node = root;
    for(char c : key.toCharArray()) {
        if(node.children.get(c) == null) {
            node.children.put(c, new TrieNode());
        }
        node = node.children.get(c);
    }
    node.value = val;
    map.put(key, val);
}

public int sum(String prefix) {
    if(prefix == null || prefix.isEmpty()) {
        return 0;
    }
    TrieNode node = root;
    for(char c : prefix.toCharArray()) {
        if(node.children.get(c) == null) {
            return 0;
        }
        node = node.children.get(c);
    }
    return dfs(node);
}

private int dfs(TrieNode node) {
    int sum = node.value;
    for(char c : node.children.keySet()) {
        sum += dfs(node.children.get(c));
    }
    return sum;
}

}

This is the final solution for the Map Sum Pairs problem on LeetCode. The time complexity of insertion and sum methods is O(n) where n is the length of key/prefix because we are traversing through each character of the key/prefix. The space complexity of the Trie data structure is O(n*l) where n is the number of keys and l is the average key length.

1