LeetCode #677 Medium

Map Sum Pairs

Design a data structure that supports inserting a key-value pair and returning the sum of all values whose keys start with a given prefix.

triehash-tabledesign

Open on LeetCode ↗

02

Intuition

A hash map can store key-value pairs, but answering 'sum all values whose keys start with this prefix' means scanning every key — O(n) per query. A trie makes prefix queries structural: walk to the node that represents the prefix, then sum the entire subtree. To make the sum even faster, store a running total at each trie node that accumulates every value that passed through it during insertion. Then sum(prefix) is a single walk to the prefix node followed by reading its total — no subtree traversal needed. The catch is handling updates: when a key is re-inserted with a new value, you must walk the old path and adjust every node by the difference.

How to spot this pattern

When a problem asks you to aggregate values over all keys sharing a prefix, the shape is a trie with augmented nodes. The prefix walk is O(prefix length) — much better than scanning all keys. The same augmented-node idea works for counting words with a prefix, or finding the key with the maximum value under a prefix.

03

Approach

1

Store each key in a trie with cumulative totals at every node

Each trie node holds a total — the sum of all values whose keys pass through this node. During insert(key, val), walk the trie character by character, creating nodes as needed. At every node on the path, add the value to total. This way, the node at the end of any prefix already holds the sum you need.

2

Handle re-insertion by tracking the delta

If a key is inserted again with a different value, you cannot just add the new value — that would count both old and new. Keep a separate hash map from key to its current value. On re-insert, compute delta = newVal - oldVal, update the hash map, then walk the trie adding delta (not newVal) to each node. This correctly adjusts the cumulative totals. For a brand-new key, the old value is 0, so delta equals the new value.

3

Answer prefix queries by reading one node

To compute sum(prefix), walk the trie character by character. If any character is missing, the prefix does not exist — return 0. Otherwise, the node you land on already holds the answer in its total field. No recursion, no subtree walk. Time is O(len(prefix)) per query.

04

Solution

▶1class MapSum:
▶2    def __init__(self):
▶3        self.trie = {}
▶4        self.map = {}
▶5 
▶6    def insert(self, key, val):
▶7        delta = val - self.map.get(key, 0)
▶8        self.map[key] = val
▶9        node = self.trie
▶10        for ch in key:
▶11            if ch not in node:
▶12                node[ch] = {'_total': 0}
▶13            node = node[ch]
▶14            node['_total'] += delta
▶15 
▶16    def sum(self, prefix):
▶17        node = self.trie
▶18        for ch in prefix:
▶19            if ch not in node:
▶20                return 0
▶21            node = node[ch]
▶22        return node['_total']

05

Common pitfalls

Adding the full value instead of the delta on re-insert

✗ Wrong

node.total += val

✓ Right

node.total += delta

If key apple was inserted with value 3 and then re-inserted with value 5, each node should increase by 2 (the delta), not by 5. Adding the full value double-counts the original insertion.

Forgetting to update the key-to-value map

✗ Wrong

# no map update
for ch in key:
    node.total += delta

✓ Right

self.map[key] = val
for ch in key:
    node.total += delta

Without updating the map, the next re-insert reads the stale old value and computes a wrong delta, causing all prefix sums to drift.

Returning 0 when the prefix walk succeeds but subtree is empty

✗ Wrong

if not node.children:
    return 0

✓ Right

return node.total

A node with no children can still have a nonzero total — it is the endpoint of a key. Checking children instead of reading the total discards valid contributions.

06

Edge cases

Re-inserting a key with a different value

The delta logic subtracts the old value and adds the new one along the entire path, so the cumulative totals stay correct.

Prefix query for a prefix that does not exist

The walk falls off the trie and returns 0 immediately.

Key inserted with value 0

Delta is 0 - oldVal, which effectively removes the old contribution. The key still exists in the trie, but its contribution to every prefix total is zero.

07

Complexity

Time

O(K) per operation

Space

O(total characters inserted)

K is the length of the key or prefix. The trie stores at most the sum of all key lengths.