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.

More Trieproblems →

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.