Map Sum Pairs

Problem Statement

The task is to design a specialized map, termed as MapSum, which facilitates two primary operations based on string keys and their corresponding numerical values. Specifically, the operations are:

• Inserting a key-value pair into the map. Should a key already exist, its value is updated to the newly provided one.
• Calculating the sum of values for all keys that start with a specified prefix.

This necessitates designing a combination of storage and retrieval methods within the MapSum class:

• MapSum(): Initializes the object environment for storing keys and values.
• void insert(String key, int val): Manages the insertion of the key-value pairs, with provision for overwriting values for existing keys.
• int sum(string prefix): Retrieves and computes the total value for all entries whose keys begin with the provided prefix.

Examples

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.

Approach and Intuition

Given the operations outlined by the problem, a direct approach using a dictionary (or hash map) can be employed to facilitate quick look-ups and updates for the insert operation. The structure ensures O(1) average-time complexity for insertions and updates. The key challenge lies in efficiently calculating the sum of values for keys that match a specific prefix, which can naturally lead to a requirement for iterating over the entire key set in the worst case, thereby having a time complexity of O(N), where N is the number of keys.

Example Strategy:

1. For the initiation of MapSum, simply establish an internal dictionary to store key-value pairs.

2. During insertion:

   • Check if the key exists in the map.
   • If it does, update the value. If not, add the new key-value pair.

3. For sum calculation:

   • Initialize a sum counter to zero.
   • Iterate over all keys in the dictionary.
   • For each key, if the prefix matches the desired starting substring, add its associated value to the sum counter.
   • Finally, return the computed sum.

This method leverages hash map efficiency for insertions and maintains clarity and correctness for prefix-based summation, which remains performant due to the small constraint bounds.

Solutions

class KeyValueStore {
    HashMap<String, Integer> store;
    Trie root;
    public KeyValueStore() {
        store = new HashMap();
        root = new Trie();
    }
    public void insert(String key, int value) {
        int difference = value - store.getOrDefault(key, 0);
        store.put(key, value);
        Trie current = root;
        current.score += difference;
        for (char c: key.toCharArray()) {
            current.children.putIfAbsent(c, new Trie());
            current = current.children.get(c);
            current.score += difference;
        }
    }
    public int sum(String prefix) {
        Trie current = root;
        for (char c: prefix.toCharArray()) {
            current = current.children.get(c);
            if (current == null) return 0;
        }
        return current.score;
    }
}
class Trie {
    Map<Character, Trie> children = new HashMap();
    int score;
}