medium

Map Sum Pairs

Keep a running total on every trie node so the sum of all values whose key starts with a prefix is a single lookup.

1. Define the problem

Map Sum Pairs

Design a store of key-value pairs that supports two actions: insert(key, val) saves a string key with a whole-number value, overwriting the value if the key was already there, and sum(prefix) returns the total of the values of every key that starts with that prefix . Store the keys in a trie, and keep a running total on every node. When you insert, walk the key down the trie and add the change in value to each node you pass. Then sum(prefix) is just a walk to one node and a single read. The "change in value" matters: if the key already had a value, adding the new value again would double-count it, so you add the difference between the new and the old value instead. Because a class cannot be written down as plain data, this exercise uses the usual interview convention for design questions: a list of operation names and a matching list of argument lists come in, and the list of results comes out. The constructor and insert produce null; sum produces a number.

Constraints

  • 1 ≤ key.length, prefix.length ≤ 50
  • key and prefix consist of lowercase English letters only
  • 1 ≤ val ≤ 1000
  • At most 50 calls in total to insert and sum

Example

Inputoperations = ["MapSum", "insert", "sum", "insert", "sum"], args = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output[null, null, 3, null, 5]

Explanation After inserting "apple" with 3, the only key starting with "ap" is "apple", so the sum is 3. After inserting "app" with 2, both "apple" and "app" start with "ap", so the sum is 3 + 2 = 5.

2. Know the words first

In plain terms

Key-value pair
A name and the thing stored under it, like "apple" -> 3.
Running total on a node
A number kept on each trie node that always equals the sum of the values of every key passing through it.
Delta
The change between the old value and the new one. Adding the delta keeps every running total correct without rebuilding anything.
3. Visualize the solution

Running totals along the path of "apple" in the trie

Running totals along the path of "apple" in the trie
Statusinit

The store starts empty: no nodes exist yet and no totals are recorded.

What happens in this step

mapSum = new MapSum()
root exists with no children
values map is empty

Every total will be built up as keys are inserted.
Step 1 of 6

Steps to visualize

  1. The row of cells is the path of the key "apple", one cell per letter.
  2. The value in each cell is that node's running total: the sum of the values of every key passing through it.
  3. Inserting adds the delta to every node along the key's path, so all totals stay correct at once.
  4. A sum is then a short walk down to the prefix node and a single read of its total.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Running totals along the path of "apple" in the trie
Statusinit

The store starts empty: no nodes exist yet and no totals are recorded.

What happens in this step

mapSum = new MapSum()
root exists with no children
values map is empty

Every total will be built up as keys are inserted.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function runMapSumOperations(operations, args) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.total = 0;
    }
  }

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

    insert(key, val) {
      const delta = val - (this.values.get(key) || 0);
      this.values.set(key, val);

      let node = this.root;
      for (const ch of key) {
        if (!node.children[ch]) {
          node.children[ch] = new TrieNode();
        }
        node = node.children[ch];
        node.total += delta;
      }

      return null;
    }

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

  const results = [];
  let mapSum = null;

  for (let i = 0; i < operations.length; i++) {
    const name = operations[i];

    if (name === 'MapSum') {
      mapSum = new MapSum();
      results.push(null);
    } else if (name === 'insert') {
      results.push(mapSum.insert(args[i][0], args[i][1]));
    } else {
      results.push(mapSum.sum(args[i][0]));
    }
  }

  return results;
}
Time
O(L) per insert and per sum, where L is the key or prefix length
Space
O(total letters across all keys)
6. Test cases

Test cases

InputExpectedCovers
operations = ["MapSum", "insert", "sum", "insert", "sum"], args = [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]][null, null, 3, null, 5]example from the docstring
operations = ["MapSum", "insert", "insert", "sum"], args = [[], ["a", 3], ["a", 2], ["a"]][null, null, null, 2]inserting the same key again replaces the value instead of adding to it
operations = ["MapSum", "insert", "sum"], args = [[], ["apple", 3], ["b"]][null, null, 0]a prefix that no key starts with gives zero
operations = ["MapSum", "sum"], args = [[], ["a"]][null, 0]asking for a sum on an empty store
operations = ["MapSum", "insert", "insert", "sum", "sum"], args = [[], ["apple", 3], ["banana", 4], ["a"], ["b"]][null, null, null, 3, 4]keys on different branches do not mix their totals
operations = ["MapSum", "insert", "insert", "insert", "sum"], args = [[], ["ab", 5], ["ac", 2], ["ab", 1], ["a"]][null, null, null, null, 3]an overwrite must also correct the totals of the shared parent nodes

Keep reading