Leetcode 677. Map Sum Pairs

Problem Explanation

You need to create a class MapSum that provides two methods: insert and sum.

The insert method accepts a string and an integer as parameters. The string is used as the key, and the integer is the associated value. If the key already exists in MapSum, the associated value will be updated to the new value.

The sum method accepts a string as a parameter, representing a prefix. The method must return the sum of all integer values whose keys start with the input prefix.

The problem can be solved by using a Trie data structure combined with a hashtable. The Trie data structure is efficient for solving problems related to prefixes, and a hashtable can be used to store and update the string-to-value mapping.

Walkthrough of the Example

According to the example given:

• insert("apple", 3) -> Here, the key 'apple' is inserted with a value of 3.
• sum("ap") -> Here we need to find the sum of all keys that start with 'ap', currently there is only one key 'apple' with a value 3, so the output is 3.
• insert("app", 2) -> Now the key 'app' is inserted with the value 2.
• sum("ap") -> Now we have two keys starting with 'ap' which are 'apple' with value 3 and 'app' with value 2, so the output is 3+2 = 5.

Solution Explanation

Let's create a class MapSum which has methods insert and sum. We will use a Trie data structure where each node represents a letter and contains an attribute sum which represents the sum of all nodes in the subtree (including the current node).

The insert operation starts by calculating the difference between the new value and the old value of the key (if it exists). Then we traverse the Trie from the root by converting the current letter to its index in the alphabet. For each letter, if the child doesn't exist, we create a new node and add it to the children array. Finally, we add the diff to the sum of all traversed nodes, and update the value of the key in the map.

The sum operation is easier, we just need to traverse the Trie according to the prefix. If at any point, the child node doesn't exist, we directly return 0. After traversing the prefix, we return the sum of the last visited node.

Now, let's move to coding part in different languages.

Python Solution

1
2python
3class TrieNode:
4    def __init__(self):
5        self.children = [None]*26
6        self.sum = 0
7
8class MapSum:
9    def __init__(self):
10        self.root = TrieNode()
11        self.map = {}
12
13    def insert(self, key: str, val: int) -> None:
14        delta = val - self.map.get(key, 0)
15        self.map[key] = val
16        curr = self.root
17        for char in key:
18            index = ord(char) - ord('a')
19            if not curr.children[index]:
20                curr.children[index] = TrieNode()
21            curr = curr.children[index]
22            curr.sum += delta
23
24    def sum(self, prefix: str) -> int:
25        curr = self.root
26        for char in prefix:
27            index = ord(char) - ord('a')
28            if not curr.children[index]:
29                return 0
30            curr = curr.children[index]
31        return curr.sum

Java Solution

1
2java
3class MapSum {
4    private TrieNode root;
5    private HashMap<String, Integer> map;
6
7    public MapSum() {
8        root = new TrieNode();
9        map = new HashMap<>();
10    }
11
12    public void insert(String key, int val) {
13        int delta = val - map.getOrDefault(key, 0);
14        map.put(key, val);
15        TrieNode curr = root;
16        for (char c : key.toCharArray()) {
17            int index = c - 'a';
18            if (curr.children[index] == null)
19                curr.children[index] = new TrieNode();
20            curr = curr.children[index];
21            curr.sum += delta;
22        }
23    }
24
25    public int sum(String prefix) {
26        TrieNode curr = root;
27        for (char c : prefix.toCharArray()) {
28            int index = c - 'a';
29            if (curr.children[index] == null)
30                return 0;
31            curr = curr.children[index];
32        }
33        return curr.sum;
34    }
35
36    class TrieNode {
37        TrieNode[] children;
38        int sum;
39
40        public TrieNode() {
41            children = new TrieNode[26];
42            sum = 0;
43        }
44    }
45}

JavaScript Solution

1
2javascript
3class TrieNode {
4    constructor() {
5        this.children = new Array(26).fill(null);
6        this.sum = 0;
7    }
8}
9
10class MapSum {
11    constructor(){
12        this.root = new TrieNode();
13        this.map = {};
14    }
15    insert(key, val) {
16        let delta = val - (this.map[key] || 0);
17        this.map[key] = val;
18        let curr = this.root;
19        for (let c of key) {
20            let index = c.charCodeAt(0) - 'a'.charCodeAt(0);
21            if (!curr.children[index]) 
22                curr.children[index] = new TrieNode();
23            curr = curr.children[index];
24            curr.sum += delta;
25        }
26    }
27    
28    sum(prefix) {
29        let curr = this.root;
30        for (let c of prefix) {
31            let index = c.charCodeAt(0) - 'a'.charCodeAt(0);
32            if (!curr.children[index]) 
33                return 0;
34            curr = curr.children[index];
35        }
36        return curr.sum;
37    }
38}

C++ Solution

1
2cpp
3class TrieNode {
4public:
5    vector<TrieNode*> children;
6    int sum;
7    TrieNode(): children(26, NULL), sum(0) {}
8};
9
10class MapSum {
11public:
12    /** Initialize your data structure here. */
13    MapSum() {
14        root = new TrieNode();
15    }
16    
17    void insert(string key, int val) {
18        int diff = val - m[key];
19        m[key] = val;
20        TrieNode* node = root;
21        for (char c : key) {
22            int i = c - 'a';
23            if (!node->children[i])
24                node->children[i] = new TrieNode();
25            node = node->children[i];
26            node->sum += diff;
27        }
28    }
29    
30    int sum(string prefix) {
31        TrieNode* node = root;
32        for (char c : prefix) {
33            int i = c - 'a';
34            if (!node->children[i])
35                return 0;
36            node = node->children[i];
37        }
38        return node->sum;
39    }
40
41private:
42    TrieNode* root;
43    unordered_map<string, int> m;
44};

C# Solution

1
2csharp
3public class TrieNode {
4    public TrieNode[] children = new TrieNode[26];
5    public int value;
6}
7
8public class MapSum {
9    TrieNode root; 
10    Dictionary<string, int> map; 
11    public MapSum() {
12        root = new TrieNode();
13        map = new Dictionary<string, int>();
14    }
15
16    public void Insert(string key, int val) {
17        int delta = val - map.GetValueOrDefault(key, 0);
18        map[key] = val;
19        TrieNode node = root;
20        foreach (char c in key) {
21            if (node.children[c - 'a'] == null) 
22                node.children[c - 'a'] = new TrieNode();
23            node = node.children[c - 'a'];
24            node.value += delta;
25        }
26    }
27
28    public int Sum(string prefix) {
29        TrieNode node = root;
30        foreach (char c in prefix) {
31            if (node.children[c - 'a'] == null) 
32                return 0;
33            node = node.children[c - 'a'];
34        }
35        return node.value;
36    }
37}

These solutions implement the problem requirements in different programming languages. Each solution utilizes the Trie data structure for efficient prefix queries, and makes use of a data map to manage the key-value pairs. However, the way to implement these features does vary by language due to syntax and built-in function differences.

For instance, in Python, Java, and JavaScript, data maps are used to calculate the difference between the new value and old value of a key with the get or getOrDefault methods.

In Python and JavaScript, ord() and charCodeAt() functions are used to find the index of a letter in the alphabet. In Java, you can directly subtract the ASCII value of 'a' from the current letter to find its index.

For the prefix sum, Python, Java, and JavaScript solutions all check if the next character in the prefix exists. If not exist, they return 0 immediately.

In the C++ solution, we use vectors for the children in each trie node and calculate the difference similar to how we did in Python, Java, JS.

The C# solution is similar to the C++ solution but uses a Dictionary for the data map and has a GetValueOrDefault method similar to Java. The structure of the TrieNode class and the logic in the insert and sum methods are almost identical to the other solutions.

The provided solutions in Python, Java, JavaScript, C++, and C# give a good range of how to solve this problem in various programming languages. The concepts remain the same - using a Trie data structure and data map in combination - but the implementation details differ according to each language's unique features.