Map Sum Pairs — DSA-30

Map Sum Pairs medium

Description

Design MapSum:

insert(key, val) — store the pair; if key already exists, overwrite its value.
sum(prefix) — return the sum of val over all keys that start with prefix.

Examples

> insert("apple", 3)
  sum("ap")          -> 3
  insert("app", 2)
  sum("ap")          -> 5      # apple(3) + app(2)
  insert("apple", 5)           # overwrite
  sum("ap")          -> 7      # apple(5) + app(2)

Constraints

1 <= key.length, prefix.length <= 50, lowercase letters.
0 <= val <= 1000, up to 50 calls each.

Intuition — two clean approaches

Approach A — prefix-sum at every node. Maintain a running sum at each node equal to the total value of all keys passing through it. On insert, add the value’s delta to every node on the path (delta handles overwrites). Then sum(prefix) is a single O(L) walk — read the prefix node’s sum.

Approach B — value at the end node + subtree DFS. Store the value only at end-of-key nodes; sum(prefix) walks to the prefix node then DFS-sums the subtree. Simpler to write, but sum is O(subtree) instead of O(L).

Approach A is the stronger answer — it makes sum as cheap as a lookup.

Code (Approach A — delta on the path)

⚠️

Handle overwrites with a delta, not by adding. If insert("apple", 3) then insert("apple", 5), naively adding 5 to every node double-counts (you’d get 8). Track each key’s current value separately and propagate new - old along the path. Forgetting the delta is the bug that passes the first example and fails the overwrite case.

Analysis

Approach A: insert O(L), sum O(L). Approach B: insert O(L), sum O(subtree).
Space: O(total key characters).

Same skin

Trie with a value field (from Variations) — this is the canonical example.
Prefix-count warm-up — same “maintain an aggregate on the insert path” trick, with a count instead of a sum.
Range-sum structures (Day 19) — the “store an aggregate so queries are O(log/L)” philosophy carried to arrays.

Replace Words Longest Word in Dictionary