How do you approach Map Sum Pairs?

Store a running total on every trie node: the sum of all keys passing through it. Then sum(prefix) is a single lookup.

What is the time complexity of Map Sum Pairs?

Time complexity: O(key length) per insert, O(prefix length) per sum.. Space complexity: O(total characters inserted).

What are common mistakes on Map Sum Pairs?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Map Sum Pairs

MediumData Structures

Description

Design a map of string keys to integer values that can sum values by prefix.

insert(key, value) stores the pair. If the key already exists, the old value is overwritten, not added to.
sum(prefix) returns the total of the values of every key starting with prefix.

Implement mapSum(operations) where operations is a list of [op, ...args]: ["insert", key, value] and ["sum", prefix]. Return one result per operation - null for insert, the total for sum.

Example 1

Input: operations = [["insert","apple",3],["sum","ap"],["insert","app",2],["sum","ap"]]

Output: [null, 3, null, 5]

Example 2

Input: operations = [["insert","a",1],["insert","a",5],["sum","a"]]

Output: [null, null, 5]

Example 3

Input: operations = [["sum","a"]]

Output: [0]

Constraints

- 1 <= key length, prefix length <= 50 - 0 <= value <= 1000 - Keys and prefixes are lowercase English letters - At most 50 operations.

Map Sum Pairs: approach, complexity and pitfalls

A medium trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

If you are stuck

Show the 3-step hint ladder

Store a running total on every trie node: the sum of all keys passing through it. Then sum(prefix) is a single lookup.
Overwrite is the trap. Adding value along the path double-counts a re-inserted key.
Keep a separate plain map of key -> current value. On insert, compute delta = newValue - (previous value or 0) and add THAT along the path.

The optimal approach

Show the approach: Store the total on the node, and propagate a delta

Put a running `total` on every trie node meaning "sum of the values of all keys passing through here". Then `sum(prefix)` is a walk down the prefix and a single read - no subtree traversal.

The hard part is not the trie, it is the overwrite semantics. If `insert` simply adds the value along the path, then re-inserting an existing key double-counts it: `insert("a", 1)` followed by `insert("a", 5)` would report 6 instead of 5.

The fix is to keep an ordinary map of `key -> current value` alongside the trie. On insert, compute `delta = newValue - (previousValue ?? 0)` and propagate the delta, not the value. For a new key the delta is the value itself; for an overwrite it is exactly the correction needed, and it works for decreases too.

This is a good example of a problem where the data structure is the easy half and the update semantics are what actually gets tested.

Time: O(key length) per insert, O(prefix length) per sum.
Space: O(total characters inserted)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.