677. Map Sum Pairs — DSA Atlas

677

MediumTrie and Advanced String SearchTrie with per-node accumulated sumsPrefix-sum aggregation in a trie

Map Sum Pairs

Design a MapSum structure supporting insert(key, val), which stores a string key with an integer value (overwriting a previous value for the same key), and sum(prefix), which returns the total of the values of all keys that start with the given prefix.

Open official problem prompt ↗

In plain English

Support fast prefix-sum queries over a growing set of key-value pairs, with correct overwrites.

Picture it like this

Like a filing cabinet where every drawer front shows the running total of all folders filed deeper inside it, updated as you file each folder.

Example

Input: insert("apple", 3); sum("ap"); insert("app", 2); sum("ap")
Output: [null, 3, null, 5]
Why: After inserting apple=3, only 'apple' starts with 'ap' (sum 3); after inserting app=2, both 'apple' and 'app' start with 'ap' (sum 5).

Constraints

1 <= key.length, prefix.length <= 50keys and prefixes consist of lowercase English letters1 <= val <= 1000At most 50 calls to insert and sum

Pattern lesson

See the pattern, then code

Prefix-sum aggregation in a trie

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Store a running sum on every node along a key's path; then sum(prefix) is just the cached total at the node the prefix ends on. Overwrites are handled by adding the delta (new value minus old value) along the path.

New words, made simpleKnow these before the algorithm

Delta: The change new_val - old_val applied when a key is re-inserted.
Node aggregate: The cached sum of all key values whose path passes through this node.
Prefix query: Reading the aggregate at the node where the prefix ends.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Store keys, scan on query

Simple but every query rescans all keys.

Keep a dict of key->val; on sum, iterate all keys checking startswith(prefix).

Time O(N * L) per sumSpace O(N * L)

Best choiceTrie with node sums

Each operation is proportional only to the key length.

Maintain a running total on each node; apply deltas on insert.

Time O(L) per opSpace O(N * L)

The rule we keep true

Invariant

Every trie node's stored total equals the sum of the current values of all inserted keys whose path passes through that node.

Why this is correct

Reasoning

Applying delta = new - old along the exact path keeps each node's total correct under overwrites, because a re-insert adjusts precisely the nodes the key touches by the amount its value changed; a prefix's total is then read directly from its end node.

The algorithm in three movesSay these aloud before coding

1Keep a map of key to current value to compute deltas on re-insert

insert apple=3: nodes a,p,p,l,e += 3

2On insert, compute delta = new_val - old_val for the key

sum('ap') -> node 'ap' total = 3

3Add delta to the sum stored on every node along the key's path (including the root aggregate)

insert app=2 -> node 'ap' total = 5

4On sum(prefix), walk to the prefix's end node and return its cached total (0 if the path is missing)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readkey='apple', val=3

2 · Askdelta?

3 · Update stateold 0 -> delta 3; add 3 to a,p,p,l,e

4 · Resultnull

Key takeaway

Node at prefix 'ap' caches the summed values of all keys passing through it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-4State
vals maps key to current value for delta computation; trie holds nodes with '#' aggregates.
2
Lines 6-14insert with delta
Compute delta versus any prior value and add it to the '#' total on each node along the key path.
3
Lines 16-22sum query
Descend to the prefix end and return its cached '#' total, or 0 if the prefix path does not exist.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Re-inserting an existing key overwrites, not adds
Querying a prefix with no matching key returns 0
A prefix equal to a full key
Inserting keys that are prefixes of each other

Common beginner mistakes

Adding val instead of the delta on overwrite, double-counting old values
Forgetting to update the map of previous values
Storing sums only at terminal nodes so prefix queries miss deeper keys
Returning 0 vs None inconsistently when the prefix is absent

Check your understanding

Why store a per-node running sum rather than recomputing on each sum() call?

PyPython 3 · solution.py

Optimal

1class MapSum:2    def __init__(self):3        self.vals = {}4        self.trie = {}56    def insert(self, key: str, val: int) -> None:7        delta = val - self.vals.get(key, 0)8        self.vals[key] = val9        node = self.trie10        node['#'] = node.get('#', 0) + delta11        for ch in key:12            node = node.setdefault(ch, {})13            node['#'] = node.get('#', 0) + delta1415    def sum(self, prefix: str) -> int:16        node = self.trie17        for ch in prefix:18            if ch not in node:19                return 020            node = node[ch]21        return node.get('#', 0)

Time complexityO(L) per insert and per sum, where L is key/prefix lengthOptimized

Space complexityO(total key characters)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleBloomberg

Map Sum Pairs

Map Sum Pairs

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search