Problem statement

Design a map from string keys to integer values that can also add up the values of all keys sharing a prefix. Write the class MapSum:

• MapSum() creates an empty map.
• void insert(String key, int value) stores the pair (key, value). If key is already present, its old value is replaced.
• int sum(String prefix) returns the sum of the values of every key that starts with prefix.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MapSum","insert","sum","insert","sum"]
[[],["apple",3],["ap"],["app",2],["ap"]]
Output: [null,null,3,null,5]
Explanation: Only "apple" starts with "ap" at first (3). After inserting "app" with 2, both keys start with "ap": 3 + 2 = 5.

Example 2

Input: ["MapSum","insert","insert","sum","insert","sum","sum"]
[[],["cat",5],["car",4],["ca"],["cat",1],["ca"],["dog"]]
Output: [null,null,null,9,null,5,0]
Explanation: "cat" and "car" give 5 + 4 = 9. Re-inserting "cat" with 1 replaces 5, so the sum drops to 1 + 4 = 5. No key starts with "dog".

Constraints

• 1 <= key.length, prefix.length <= 50
• key and prefix consist of only lowercase English letters
• 1 <= value <= 1000
• At most 50 calls are made to insert and sum

Hints for Map Sum Pairs

1. Hint 1

   Summing over every stored key on each query works, but a trie lets the prefix itself lead you to exactly the keys that share it.

2. Hint 2

   Store at every trie node the total value of all keys passing through it; then sum(prefix) is the total at the prefix's node.

3. Hint 3

   Re-inserting a key must replace its value: remember each key's current value and add only the difference value - old along its path.

How to solve Map Sum Pairs

A trie whose every node carries the sum of the values of all keys passing through it. A query walks the prefix and reads one number; an insert walks its key and adds the change in that key's value to every node on the way.

Approach

1. Each node holds children, total (sum over keys through it) and own (the value of the key ending exactly here, 0 if none).
2. insert(key, value): walk key, creating missing nodes, to its last node; let delta = value - own, set own = value.
3. Walk key again from the root and add delta to total of every node on the path.
4. sum(prefix): walk prefix; if a child is missing return 0, otherwise return the last node's total.

Why it works

A key's value contributes to the total of exactly the nodes on its path, which are the nodes of its prefixes. Adding delta keeps every such total equal to the sum of the current values, because the old value was counted there and is replaced by the new one. The node of prefix therefore holds the sum over all keys starting with prefix.

Complexity

• Time — O(L) per insert and per sum, L = length of the string
• Space — O(total letters inserted)

Pitfalls

• Adding value instead of value - old double-counts a key that is inserted twice.
• A prefix with no node in the trie sums to 0, not to an error.

Reference solution

Python

class MapSum:

    def __init__(self):
        # letter -> child; "#" = total of the keys through this node, "=" = value of the key ending here
        self.root = {"#": 0}

    def insert(self, key: str, value: int) -> None:
        path = [self.root]
        for ch in key:
            path.append(path[-1].setdefault(ch, {"#": 0}))
        delta = value - path[-1].get("=", 0)
        path[-1]["="] = value
        for node in path:
            node["#"] += delta

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

Java

class MapSum {
    private static class Node {
        Node[] next = new Node[26];
        int total, own;
    }

    private Node root = new Node();

    public MapSum() {
    }

    public void insert(String key, int value) {
        Node node = root;
        for (int i = 0; i < key.length(); i++) {
            int c = key.charAt(i) - 'a';
            if (node.next[c] == null) node.next[c] = new Node();
            node = node.next[c];
        }
        int delta = value - node.own;
        node.own = value;
        node = root;
        root.total += delta;
        for (int i = 0; i < key.length(); i++) {
            node = node.next[key.charAt(i) - 'a'];
            node.total += delta;
        }
    }

    public int sum(String prefix) {
        Node node = root;
        for (int i = 0; i < prefix.length() && node != null; i++) node = node.next[prefix.charAt(i) - 'a'];
        return node == null ? 0 : node.total;
    }
}

C++

class MapSum {
    struct Node {
        Node* next[26] = {};
        int total = 0, own = 0;
    };
    Node* root = new Node();
public:
    MapSum() {}

    void insert(string key, int value) {
        vector<Node*> path{root};
        for (char ch : key) {
            Node*& child = path.back()->next[ch - 'a'];
            if (!child) child = new Node();
            path.push_back(child);
        }
        int delta = value - path.back()->own;
        path.back()->own = value;
        for (Node* node : path) node->total += delta;
    }

    int sum(string prefix) {
        Node* node = root;
        for (size_t i = 0; i < prefix.size() && node; i++) node = node->next[prefix[i] - 'a'];
        return node ? node->total : 0;
    }
};

JavaScript

var MapSum = function() {
    this.root = { children: {}, total: 0, own: 0 };
};

MapSum.prototype.insert = function(key, value) {
    var path = [this.root], node = this.root;
    for (var i = 0; i < key.length; i++) {
        var ch = key[i];
        if (!node.children[ch]) node.children[ch] = { children: {}, total: 0, own: 0 };
        node = node.children[ch];
        path.push(node);
    }
    var delta = value - node.own;
    node.own = value;
    for (var k = 0; k < path.length; k++) path[k].total += delta;
};

MapSum.prototype.sum = function(prefix) {
    var node = this.root;
    for (var i = 0; i < prefix.length; i++) {
        node = node.children[prefix[i]];
        if (!node) return 0;
    }
    return node.total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium