Map Sum Pairs — Trie with Cumulative Sum Propagation

Problem Statement#

LeetCode 677 — Map Sum Pairs | Difficulty: Medium

Design a MapSum class that supports two operations:

• MapSum() — initialise the structure.
• void insert(String key, int val) — insert the key-val pair. If key already existed, overwrite its value.
• int sum(String prefix) — return the sum of all values whose keys start with prefix.

Example:

MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap");           → 3
mapSum.insert("app",   2);
mapSum.sum("ap");           → 5    ("apple"=3 + "app"=2)
mapSum.insert("apple", 5);  // overwrite
mapSum.sum("ap");           → 7    ("apple"=5 + "app"=2)

Constraints:

• 1 <= key.length, prefix.length <= 50
• 1 <= val <= 1000
• At most 50 calls to insert and sum.

Why This Problem Matters#

Map Sum Pairs is the canonical cumulative-trie design problem, asked at Amazon, Google, Bloomberg, and Akuna Capital. It is a sibling of LeetCode 2416 (Sum of Prefix Scores) but with values instead of counts and with mutability (overwrite semantics) layered on top. Mastering it earns you the design-trie pattern that powers production autocomplete services, weighted search suggestions, and prefix-aggregated metrics dashboards.

The "store delta and propagate" technique generalises far beyond tries. It appears in segment trees with lazy propagation, prefix sum arrays under updates, and incremental aggregation in databases. Recognising the shared pattern is exactly what senior interviewers probe.

The Core Insight#

Two design moves combine:

1. Augment each trie node with a total field = sum of values for all keys passing through. Then sum(prefix) is a plain trie walk that returns node.total at the prefix end. O(prefix length).
2. Handle overwrite via a delta — keep a side hashmap vals[key] = previous value. On insert(key, val), compute delta = val - vals.get(key, 0), update vals[key] = val, and add delta (not val) to every total along the trie path.

The delta trick avoids a second walk to subtract the old value. If the key is new, delta = val. If it is being overwritten, delta may be positive or negative — both work.

Why O(L) per operation? Insert touches L nodes (one per character). Sum touches at most L nodes (walks down to prefix tip). No subtree DFS needed.

Visual Dry Run#

Operations:

insert("apple", 3) → vals = {"apple":3}, delta = 3
insert("app",   2) → vals = {"apple":3,"app":2}, delta = 2
insert("apple", 5) → vals = {"apple":5,"app":2}, delta = 5 - 3 = +2

Trie state after all inserts:

root (total = 0)
 |-- a (total = 7)
      |-- p (total = 7)
           |-- p (total = 7)
                |-- l (total = 5)
                     |-- e (total = 5)

Walk for sum("ap") → reach node 'p' (depth 2), return total = 7. Walk for sum("app") → reach inner 'p' (depth 3), return total = 7. Walk for sum("apple") → reach 'e' (depth 5), return total = 5.

The delta of +2 on the third insert flowed cleanly through nodes 'a', 'p', 'p', 'l', 'e' — exactly the nodes already on the path of "apple". Nodes outside the path were untouched.

Solution (Optimal) — Trie with Delta Propagation#

Python#

class TrieNode:
    __slots__ = ("children", "total")
    def __init__(self):
        self.children = {}
        self.total = 0
 
class MapSum:
    def __init__(self):
        self.root = TrieNode()
        self.vals = {}   # key -> previously inserted value (for delta)
 
    def insert(self, key: str, val: int) -> None:
        delta = val - self.vals.get(key, 0)
        self.vals[key] = val
        node = self.root
        for ch in key:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.total += delta
 
    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.total

JavaScript#

class TrieNode {
  constructor() {
    this.children = {};
    this.total = 0;
  }
}
 
class MapSum {
  constructor() {
    this.root = new TrieNode();
    this.vals = new Map();
  }
  insert(key, val) {
    const delta = val - (this.vals.get(key) ?? 0);
    this.vals.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;
    }
  }
  sum(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return 0;
      node = node.children[ch];
    }
    return node.total;
  }
}

Complexity#

• Insert: O(L) where L = key length.
• Sum: O(P) where P = prefix length.
• Space: O(total characters across all keys).

Common Mistakes#

1. Adding val instead of delta on overwrite — double-counts. The first insert("apple", 3) followed by insert("apple", 5) would store 8, not 5.
2. Forgetting the side vals map — without remembering the previous value, you cannot compute delta correctly.
3. Storing values only at terminal nodes and DFS'ing on each sum — works but sum() becomes O(subtree size), which fails the constraints if the trie is dense.
4. Initialising total lazily without 0 — JavaScript undefined arithmetic produces NaN; always initialise.
5. Using a global counter and recomputing from scratch each insert — O(N times L) per insert and unnecessary.
6. Treating the prefix walk as needing to terminate at a key end — sum() walks to the last char of the prefix only, regardless of whether a key ends there.

Interview Tips#

• Lead with the alternative: hashmap of all keys + linear scan per sum. Acknowledge it works but is O(N times L) per query.
• Pitch the trie augmentation: "Each node carries a running total of values along its subtree. A sum query is just a walk."
• Make the delta trick explicit: say "On overwrite, we add (new - old) so we do not need a second walk."
• Mention that the side vals map handles overwrite correctly with O(1) memory per key.
• For follow-ups, mention that this generalises to "top-k by value with prefix" via heap or sorted set per node.

Follow-up Questions#

• Delete a key? insert(key, 0) works — propagates -old along the path. Optionally clean up empty nodes.
• Top-k keys with prefix sorted by value? Per-node sorted structure or DFS the subtree, sort, take top-k.
• What if values can be negative? The algorithm is unchanged — deltas can be negative; totals can be negative.
• Range sum (sum over keys in [lo, hi])? Trie does not support range elegantly; switch to a balanced BST or order-statistic tree.
• Persistence (versioned MapSum)? Use immutable trie nodes with path copying — each insert creates O(L) new nodes.

Key Takeaways#

• Map Sum Pairs uses a counted trie augmented with cumulative total at every node.
• The delta trick delta = new - old handles overwrite in a single walk.
• Insert and sum are both O(L) — independent of total key count.
• Always pair the trie with a side vals map to remember previous values for deltas.
• This template powers weighted autocomplete, prefix-aggregated metrics, and FAANG search ranking services.
• Recognising the "delta + lazy propagation" pattern unlocks segment trees, lazy DS, and many advanced trie variants.