Code Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.value = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()
        self.map = {}

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)
        self.map[key] = val
        node = self.root
        for c in key:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
            node.value += delta

    def sum(self, prefix: str) -> int:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        return node.value
      

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    int value = 0;
};

class MapSum {
    TrieNode* root;
    unordered_map<string, int> map;
public:
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        int delta = val - map[key];
        map[key] = val;
        TrieNode* node = root;
        for (char c : key) {
            if (!node->children.count(c))
                node->children[c] = new TrieNode();
            node = node->children[c];
            node->value += delta;
        }
    }
    
    int sum(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c))
                return 0;
            node = node->children[c];
        }
        return node->value;
    }
};
      

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int value = 0;
}

class MapSum {
    TrieNode root;
    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 node = root;
        for (char c : key.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
            node.value += delta;
        }
    }
    
    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c))
                return 0;
            node = node.children.get(c);
        }
        return node.value;
    }
}
      

class TrieNode {
    constructor() {
        this.children = {};
        this.value = 0;
    }
}

class MapSum {
    constructor() {
        this.root = new TrieNode();
        this.map = {};
    }

    insert(key, val) {
        let delta = val - (this.map[key] || 0);
        this.map[key] = val;
        let node = this.root;
        for (let c of key) {
            if (!node.children[c]) {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
            node.value += delta;
        }
    }

    sum(prefix) {
        let node = this.root;
        for (let c of prefix) {
            if (!node.children[c]) return 0;
            node = node.children[c];
        }
        return node.value;
    }
}
      

Problem Description

The Map Sum Pairs problem requires you to design a data structure that supports two operations:

• insert(key, val): Insert the string key with integer value val into the data structure. If the key already exists, update its value to val.
• sum(prefix): Return the sum of all the values of keys that start with the given prefix.

The key constraints are:

• Each key is a non-empty string of lowercase letters.
• Each val is an integer.
• When a key is updated, its previous value is replaced.
• The sum operation must efficiently return the sum of all values for keys with the given prefix.

Thought Process

At first glance, the problem seems similar to working with a regular map or dictionary. You could store each key with its val and, for a sum(prefix) query, iterate through all keys and add up values for those starting with the prefix.

However, this brute-force approach is inefficient, especially if there are many keys or frequent sum queries. We need an optimized way to quickly find and sum all values of keys sharing a common prefix.

This leads us to consider data structures designed for prefix-based operations. A trie (prefix tree) is a natural fit, as it allows us to traverse only the relevant parts of the key space for a given prefix.

Solution Approach

To solve the problem efficiently, we use a combination of a trie (prefix tree) and a hash map:

• Trie Structure: Each node in the trie represents a character and holds a value field, which is the sum of all vals for keys that pass through that node. This allows us to quickly compute the sum of all keys with a given prefix by traversing the trie to the end of the prefix and returning the stored sum.
• Hash Map: We also maintain a hash map to store the current value for each key. This is necessary because if a key is updated, we need to adjust the sums along the trie path by the correct delta (difference between new and old value), not just by the new value.

Step-by-step algorithm:

1. Insert Operation:
   • Compute the difference (delta) between the new value and the existing value for the key (if any).
   • Update the hash map with the new value.
   • Traverse the trie along the path of the key, creating nodes as needed.
   • At each node, add delta to its value field.
2. Sum Operation:
   • Traverse the trie following the prefix.
   • If the prefix exists, return the value at the last node of the prefix.
   • If any character in the prefix is missing in the trie, return 0.

This approach ensures that both insert and sum operations are efficient and scale well with the number of keys and queries.

Example Walkthrough

Let's walk through an example step by step:

• insert("apple", 3):
  - The trie is empty, so we create nodes for 'a', 'p', 'p', 'l', 'e'.
  - At each node, we add 3 to the value field.
  - The hash map records {"apple": 3}.
• sum("ap"):
  - We traverse 'a' and 'p' in the trie.
  - The node for 'p' has value = 3 (from "apple").
  - Return 3.
• insert("app", 2):
  - The prefix 'a', 'p', 'p' already exists.
  - The delta is 2 (since "app" is new).
  - Add 2 to each of the nodes for 'a', 'p', 'p'.
  - The node for 'p' (the second 'p') now has value = 5.
  - The hash map records {"apple": 3, "app": 2}.
• sum("ap"):
  - Traverse 'a' and 'p'.
  - The node for 'p' now has value = 5 (3 from "apple" + 2 from "app").
  - Return 5.
• insert("apple", 2):
  - "apple" exists with value 3, so delta is -1.
  - Subtract 1 from each node along "apple".
  - The hash map updates to {"apple": 2, "app": 2}.
• sum("ap"):
  - Node for 'p' now has value = 4 (2 from "apple" + 2 from "app").
  - Return 4.

Time and Space Complexity

• Brute-force approach:
  • insert: O(1)
  • sum: O(N * L), where N is the number of keys and L is the average key length (need to check each key for the prefix)
• Optimized (Trie) approach:
  • insert: O(L), where L is the length of the key (walk the trie and update each node)
  • sum: O(P), where P is the length of the prefix (just walk the prefix in the trie)
  • Space complexity: O(Total characters in all keys) for the trie, plus O(N) for the map storing key-value pairs.

The trie-based approach is much more efficient for frequent sum queries, especially as the number of keys grows.

Summary

The Map Sum Pairs problem is elegantly solved by combining a trie (for fast prefix-based aggregation) with a hash map (for tracking current key values and computing updates). This hybrid structure allows both insert and sum operations to be performed efficiently, avoiding the pitfalls of brute-force scanning. The key insight is to store running sums at each trie node and update them with the correct delta when key values change, ensuring both correctness and performance.