# Map Sum Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/map-sum-pairs)
Canonical: https://scaleengineer.com/dsa/problems/map-sum-pairs
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, String, Trie
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
Design a map that allows you to do the following:

* Maps a string key to a given value.
* Returns the sum of the values that have a key with a prefix equal to a given string.

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 1:**

**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)

**Constraints:**

* `1 <= key.length, prefix.length <= 50`
* `key` and `prefix` consist of only lowercase English letters.
* `1 <= val <= 1000`
* At most `50` calls will be made to `insert` and `sum`.

# Approaches
## Brute Force with HashMap
This approach uses a standard `HashMap` to store the key-value pairs. The `insert` operation is straightforward, mapping directly to the `put` method of the hash map. To calculate the sum for a given prefix, we iterate through all the keys in the map, check if each key starts with the prefix, and accumulate the values of the matching keys.
**Time:** - `insert(key, val)`: O(L), where L is the length of the `key`. This is the time taken to compute the hash of the string.
- `sum(prefix)`: O(N * P), where N is the number of keys in the map and P is the length of the `prefix`. We iterate through all N keys, and for each, `startsWith` takes O(P) time. · **Space:** O(K), where K is the total number of characters across all keys stored in the map. This is because the map needs to store all the key strings.
**Pros:** Very simple to implement and understand.; Low memory overhead if the number of keys is small.
**Cons:** The `sum` operation is inefficient, especially for a large number of keys, as it requires a full scan of all stored keys.
### Explanation
The simplest way to solve this problem is by using a `HashMap` to store the mapping from a string `key` to an integer `val`.

**`insert(key, val)` operation:**
This operation is very simple. We just place the `(key, val)` pair into our hash map. If the key already exists, the `put` operation will automatically overwrite the old value with the new one, which is the desired behavior.

**`sum(prefix)` operation:**
For this operation, we need to find all keys that start with the given `prefix`. Since the hash map doesn't provide a direct way to query by prefix, we have to iterate through its entire set of keys. For each key, we check if it has the given `prefix` using the `String.startsWith()` method. If it does, we add the key's associated value to a running sum. Finally, we return this sum.

```java
import java.util.HashMap;
import java.util.Map;

class MapSum {
    private 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 totalSum = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getKey().startsWith(prefix)) {
                totalSum += entry.getValue();
            }
        }
        return totalSum;
    }
}
```
### Algorithm
- In the constructor, initialize a `HashMap<String, Integer>` to store the key-value pairs.
- For the `insert(String key, int val)` method:
  - Use the map's `put` method to insert or update the key-value pair: `map.put(key, val)`.
- For the `sum(String prefix)` method:
  - Initialize a variable `totalSum` to 0.
  - Iterate through every entry (`key`, `value`) in the HashMap.
  - For each key, use the `startsWith()` method to check if it begins with the given `prefix`.
  - If `key.startsWith(prefix)` is true, add the corresponding `value` to `totalSum`.
  - After checking all keys, return `totalSum`.

## Trie with DFS for Sum
A more optimized approach involves using a Trie (Prefix Tree). A Trie is a tree-like data structure perfect for handling prefix-based searches. Each node represents a character, and a path from the root to a node represents a prefix. We store the actual value of a key at the node where the key ends.

To calculate the sum, we first navigate to the node representing the given prefix. Then, we perform a traversal (like DFS or BFS) on the entire subtree rooted at this prefix node, summing up the values of all words we find.
**Time:** - `insert(key, val)`: O(L), where L is the length of the `key`.
- `sum(prefix)`: O(P + M), where P is the length of the `prefix` and M is the number of nodes in the subtree rooted at the prefix node. In the worst case, M can be the total number of nodes in the Trie. · **Space:** O(K), where K is the total number of characters across all keys. In the worst case, if no keys share prefixes, the space is proportional to the sum of the lengths of all keys.
**Pros:** Efficient `insert` operation.; Generally faster `sum` operation than the brute-force approach, especially for longer prefixes that prune the search space significantly.
**Cons:** The `sum` operation can be slow if the prefix is short (e.g., an empty string) or if the subtree under the prefix is large, as it requires traversing all nodes in that subtree.
### Explanation
A Trie is a natural fit for this problem. We can build a Trie where each node has an array or map of children (one for each possible character) and a `value` field.

**`TrieNode` Structure:**
Each `TrieNode` will contain:
1.  `children`: A map or an array of `TrieNode`s (e.g., `TrieNode[26]`).
2.  `value`: An integer that stores the value of the key that ends at this specific node. It's 0 if no key ends here.

**`insert(key, val)` operation:**
We traverse the Trie from the root, one character at a time. If a character's corresponding node doesn't exist, we create it. After processing all characters of the key, we arrive at the final node and set its `value` field to `val`. This handles both new insertions and updates.

**`sum(prefix)` operation:**
First, we traverse the Trie to locate the node that corresponds to the end of the `prefix`. If this path doesn't exist, no keys have this prefix, so we return 0. If the node is found, we then need to sum the values of all keys that pass through or end at this node. We can do this by performing a recursive Depth First Search (DFS) starting from this prefix node. The DFS will explore the entire subtree, and for every node it visits, it adds the node's `value` to a running total.

```java
class MapSum {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int value = 0;
    }

    private TrieNode root;

    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode curr = root;
        for (char c : key.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new TrieNode();
            }
            curr = curr.children[c - 'a'];
        }
        curr.value = val;
    }
    
    public int sum(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                return 0;
            }
            curr = curr.children[c - 'a'];
        }
        return dfsSum(curr);
    }

    private int dfsSum(TrieNode node) {
        if (node == null) {
            return 0;
        }
        int currentSum = node.value;
        for (TrieNode child : node.children) {
            currentSum += dfsSum(child);
        }
        return currentSum;
    }
}
```
### Algorithm
- Define a `TrieNode` class containing a `children` map (or array) and an integer `value` which stores the value of the key ending at this node.
- In the `MapSum` constructor, initialize a root `TrieNode`.
- For `insert(key, val)`:
  - Traverse the trie from the root, character by character.
  - Create new nodes for characters not yet in the trie.
  - At the node corresponding to the last character of the key, set its `value` field to `val`.
- For `sum(prefix)`:
  - Traverse the trie to find the node corresponding to the end of the `prefix`. Let's call it `prefixNode`.
  - If `prefixNode` does not exist, return 0.
  - Perform a traversal (e.g., Depth First Search) starting from `prefixNode` to visit all nodes in its subtree.
  - During the traversal, sum up the `value` fields of all visited nodes. This sum is the result.

## Optimized Trie with Precomputed Path Sums
This is the most efficient approach, which optimizes the `sum` operation significantly. We modify the Trie so that each node stores the sum of all values in its entire subtree. This way, the sum for any prefix is pre-calculated and can be retrieved in time proportional to the prefix length.

To handle updates correctly (e.g., changing the value of an existing key), we also maintain a separate `HashMap` to keep track of the current value of each key. When a key is inserted or updated, we calculate the change in value (`delta`) and propagate this `delta` through the Trie, updating the `sum` at each node along the key's path.
**Time:** - `insert(key, val)`: O(L), where L is the length of the `key`.
- `sum(prefix)`: O(P), where P is the length of the `prefix`. · **Space:** O(K), where K is the total number of characters across all keys. The space is used by the Trie and the auxiliary HashMap, both of which depend on the keys' content and length.
**Pros:** Extremely fast `sum` operation, making it ideal for scenarios with frequent sum queries.; The `insert` operation remains efficient.
**Cons:** Higher space complexity due to the need for both a Trie and an auxiliary HashMap.; The `insert` logic is more complex than in other approaches.
### Explanation
This approach enhances the Trie by pre-calculating sums to make the `sum` query extremely fast.

**`TrieNode` Structure:**
Each `TrieNode` will contain:
1.  `children`: A map or an array of `TrieNode`s.
2.  `sum`: An integer that stores the sum of values of all keys that pass through or end in this node's subtree.

**Data Structures:**
We use two main data structures:
1.  The modified Trie described above.
2.  A `HashMap<String, Integer>` to store the actual value for each inserted key. This is crucial for handling updates.

**`insert(key, val)` operation:**
When inserting a `(key, val)` pair, we need to update the sums along the key's path in the Trie. If we are updating an existing key, the contribution to the prefix sums changes. We calculate this change, or `delta`, as `newValue - oldValue`. The `oldValue` is retrieved from our auxiliary HashMap (it's 0 for a new key). We then traverse the Trie for the `key`, and for every node on the path, we add this `delta` to its `sum` field. Finally, we update the key's value in the HashMap.

**`sum(prefix)` operation:**
This becomes very efficient. We simply traverse the Trie to the node corresponding to the `prefix`. The `sum` field of this node already holds the total sum of all keys starting with that prefix. We just return this value. If the prefix path does not exist in the Trie, the sum is 0.

```java
import java.util.HashMap;
import java.util.Map;

class MapSum {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int sum = 0; // Sum of all values in this subtree
    }

    private TrieNode root;
    private Map<String, Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        
        TrieNode curr = root;
        for (char c : key.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new TrieNode();
            }
            curr = curr.children[c - 'a'];
            curr.sum += delta;
        }
    }
    
    public int sum(String prefix) {
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            if (curr.children[c - 'a'] == null) {
                return 0;
            }
            curr = curr.children[c - 'a'];
        }
        return curr.sum;
    }
}
```
### Algorithm
- Define a `TrieNode` class with a `children` map/array and an integer `sum` field.
- In the `MapSum` class, initialize a root `TrieNode` and a `HashMap<String, Integer>` to store the actual key-value pairs.
- For `insert(key, val)`:
  - Check the auxiliary map to find the previous value of the key (0 if it's a new key).
  - Calculate the difference: `delta = newValue - oldValue`.
  - Traverse the trie for the given `key`. For each node on the path, add `delta` to its `sum` field.
  - Finally, update the key's value in the auxiliary map: `map.put(key, val)`.
- For `sum(prefix)`:
  - Traverse the trie to find the node corresponding to the end of the `prefix`.
  - If the path doesn't exist, return 0.
  - Otherwise, return the `sum` field of the final node. This value is the precomputed sum for that prefix.

# Solutions
### CSharp

```csharp
public class Trie { private Trie [] children = new Trie [ 26 ]; private int val ; public void Insert ( string w , int x ) { Trie node = this ; for ( int i = 0 ; i < w . Length ; ++ i ) { int idx = w [ i ] - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; node . val += x ; } } public int Search ( string w ) { Trie node = this ; for ( int i = 0 ; i < w . Length ; ++ i ) { int idx = w [ i ] - 'a' ; if ( node . children [ idx ] == null ) { return 0 ; } node = node . children [ idx ]; } return node . val ; } } public class MapSum { private Dictionary < string , int > d = new Dictionary < string , int >(); private Trie trie = new Trie (); public MapSum () { } public void Insert ( string key , int val ) { int x = val - ( d . ContainsKey ( key ) ? d [ key ] : 0 ); d [ key ] = val ; trie . Insert ( key , x ); } public int Sum ( string prefix ) { return trie . Search ( prefix ); } } /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.Insert(key,val); * int param_2 = obj.Sum(prefix); */
```

### Java

```java
class Trie { private Trie [] children = new Trie [ 26 ]; private int val ; public void insert ( String w , int x ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { node . children [ idx ] = new Trie (); } node = node . children [ idx ]; node . val += x ; } } public int search ( String w ) { Trie node = this ; for ( int i = 0 ; i < w . length (); ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { return 0 ; } node = node . children [ idx ]; } return node . val ; } } class MapSum { private Map < String , Integer > d = new HashMap <>(); private Trie trie = new Trie (); public MapSum () { } public void insert ( String key , int val ) { int x = val - d . getOrDefault ( key , 0 ); d . put ( key , val ); trie . insert ( key , x ); } public int sum ( String prefix ) { return trie . search ( prefix ); } } /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */
```

### JavaScript

```javascript
class Trie { constructor () { this . children = new Array ( 26 ); this . val = 0 ; } insert ( w , x ) { let node = this ; for ( const c of w ) { const i = c . charCodeAt ( 0 ) - 97 ; if ( ! node . children [ i ]) { node . children [ i ] = new Trie (); } node = node . children [ i ]; node . val += x ; } } search ( w ) { let node = this ; for ( const c of w ) { const i = c . charCodeAt ( 0 ) - 97 ; if ( ! node . children [ i ]) { return 0 ; } node = node . children [ i ]; } return node . val ; } } var MapSum = function () { this . d = new Map (); this . t = new Trie (); }; /** * @param {string} key * @param {number} val * @return {void} */ MapSum . prototype . insert = function ( key , val ) { const x = val - ( this . d . get ( key ) ?? 0 ); this . d . set ( key , val ); this . t . insert ( key , x ); }; /** * @param {string} prefix * @return {number} */ MapSum . prototype . sum = function ( prefix ) { return this . t . search ( prefix ); }; /** * Your MapSum object will be instantiated and called as such: * var obj = new MapSum() * obj.insert(key,val) * var param_2 = obj.sum(prefix) */
```

### CPP

```cpp
class Trie { public: Trie () : children ( 26 , nullptr ) { } void insert ( string & w , int x ) { Trie * node = this ; for ( char c : w ) { c -= 'a' ; if ( ! node -> children [ c ]) { node -> children [ c ] = new Trie (); } node = node -> children [ c ]; node -> val += x ; } } int search ( string & w ) { Trie * node = this ; for ( char c : w ) { c -= 'a' ; if ( ! node -> children [ c ]) { return 0 ; } node = node -> children [ c ]; } return node -> val ; } private: vector < Trie *> children ; int val = 0 ; }; class MapSum { public: MapSum () { } void insert ( string key , int val ) { int x = val - d [ key ]; d [ key ] = val ; trie -> insert ( key , x ); } int sum ( string prefix ) { return trie -> search ( prefix ); } private: unordered_map < string , int > d ; Trie * trie = new Trie (); }; /** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */
```

### Python

```python
class Trie : def __init__ ( self ): self . children : List [ Trie | None ] = [ None ] * 26 self . val : int = 0 def insert ( self , w : str , x : int ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . val += x def search ( self , w : str ) -> int : node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return 0 node = node . children [ idx ] return node . val class MapSum : def __init__ ( self ): self . d = defaultdict ( int ) self . tree = Trie () def insert ( self , key : str , val : int ) -> None : x = val - self . d [ key ] self . d [ key ] = val self . tree . insert ( key , x ) def sum ( self , prefix : str ) -> int : return self . tree . search ( prefix ) # Your MapSum object will be instantiated and called as such: # obj = MapSum() # obj.insert(key,val) # param_2 = obj.sum(prefix)
```