Log inSign up
mediumLeetCodeNot Started

Map Sum Pairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

Design a map that allows you to insert a new (key, val) pair and sum the values of all existing keys that have a given prefix.

Implement the MapSum class: - MapSum() Initializes the MapSum object. - void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-val pair will be overridden to the new val. - int sum(String prefix) Returns the sum of all the pairs' value whose key starts with the prefix.

Example 1 · Example 1: Insert, Override, and Sum:

Input: ["MapSum", "insert", "sum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"], ["apple", 5], ["ap"]]
Output: [null, null, 3, null, 5, null, 7]
Explanation: 1. insert("apple", 3): path a-p-p-l-e gets score += 3. 2. sum("ap") -> node p has score 3. 3. insert("app", 2): path a-p-p gets score += 2. Node p score = 3 + 2 = 5. 4. sum("ap") -> 5. 5. insert("apple", 5): override! delta = 5 - 3 = 2. Path apple gets score += 2. Node p score = 5 + 2 = 7. 6. sum("ap") -> 7.

Constraints:

  • 1 <= key.length, prefix.length <= 50
  • key and prefix consist of only lowercase English letters.
  • 1 <= val <= 1000
  • At most 50 calls will be made to insert and sum in typical tests (up to 104 in stress tests).

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Manage value override semantics in an aggregated prefix tree.
  • Propagate incremental score deltas down Trie paths during insertion.
  • Achieve O(Prefix) query time for subtree aggregate calculations.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Insert key-value pairs with override semantics.
  • Query sum of values of all keys matching a prefix.
  • Strict time constraints requiring instant prefix sum retrieval.

Algorithmic Decision Tree:

  • Track delta = val - oldVal using a secondary hash map.
  • Each TrieNode maintains integer score representing sum of all keys passing through it.
  • sum(prefix) traverses characters of prefix and returns node.score directly.

Connected Patterns:

Implement TrieSearch Suggestions SystemDesign Add and Search Words Data Structure

1. Hash Map Key Iteration

Intuition

Maintain unordered_map<string, int>. insert updates map[key] = val. sum(prefix) loops through all entries: if entry.key.startsWith(prefix), adds entry.val to sum.

When to apply: Quick brute force baseline.

Algorithm

  1. Step 1: Store map[key] = val.
  2. Step 2: On sum(prefix): initialize total = 0.
  3. Step 3: For each [k, v] in map: if k.startsWith(prefix), total += v.
  4. Step 4: Return total.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6class MapSum {
7 unordered_map<string, int> store;
8public:
9 MapSum() {}
10
11 void insert(string key, int val) {
12 store[key] = val;
13 }
14
15 int sum(string prefix) {
16 int total = 0;
17 for (const auto& [k, v] : store) {
18 if (k.rfind(prefix, 0) == 0) {
19 total += v;
20 }
21 }
22 return total;
23 }
24};
25
26int main() {
27 MapSum mapSum;
28 mapSum.insert("apple", 3);
29 cout << "sum('ap'): " << mapSum.sum("ap") << endl;
30 mapSum.insert("app", 2);
31 cout << "sum('ap'): " << mapSum.sum("ap") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: insert: O(1), sum: O(N * Prefix) — Must inspect all N keys in the map for each sum query.
  • Space complexity: O(N * L) — Stores all N keys and values.

Why Brute Force Doesn't Scale:

With 10,000 descendant words, subtree traversal visits 100,000 nodes per sum call.

Precomputing scores along the insertion path reduces sum queries to an instant O(Prefix) read.

2. Trie with Subtree DFS Traversal

Intuition

Store words in Trie with integer val at terminal nodes. sum(prefix) traverses characters of prefix. If prefix exists, execute DFS from the prefix node summing node.val across the entire subtree.

When to apply: When memory must be minimized and sum queries are infrequent.

Algorithm

  1. Step 1: Standard Trie with integer val = 0.
  2. Step 2: insert: walk path, set curr.val = val at final node.
  3. Step 3: sum: walk to prefix node. If null, return 0.
  4. Step 4: Run DFS from prefix node summing all child.val.
  5. Step 5: Return sum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3using namespace std;
4
5struct TrieNode {
6 TrieNode* children[26];
7 int val;
8 TrieNode() : val(0) {
9 for (int i = 0; i < 26; i++) children[i] = nullptr;
10 }
11};
12
13class MapSum {
14 TrieNode* root;
15
16 int dfs(TrieNode* node) {
17 if (!node) return 0;
18 int total = node->val;
19 for (int i = 0; i < 26; i++) {
20 if (node->children[i]) total += dfs(node->children[i]);
21 }
22 return total;
23 }
24
25public:
26 MapSum() {
27 root = new TrieNode();
28 }
29
30 void insert(string key, int val) {
31 TrieNode* curr = root;
32 for (char c : key) {
33 int idx = c - 'a';
34 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
35 curr = curr->children[idx];
36 }
37 curr->val = val;
38 }
39
40 int sum(string prefix) {
41 TrieNode* curr = root;
42 for (char c : prefix) {
43 int idx = c - 'a';
44 if (!curr->children[idx]) return 0;
45 curr = curr->children[idx];
46 }
47 return dfs(curr);
48 }
49};
50
51int main() {
52 MapSum mapSum;
53 mapSum.insert("apple", 3);
54 cout << "sum('ap'): " << mapSum.sum("ap") << endl;
55 mapSum.insert("app", 2);
56 cout << "sum('ap'): " << mapSum.sum("ap") << endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: insert: O(L), sum: O(Prefix + Subtree Nodes) — Query must visit every node in the subtree rooted at the prefix.
  • Space complexity: O(Total characters * 26) — Trie pointer overhead.

3. Trie with Precalculated Score & Delta Tracking

Intuition

Maintain a map of key -> val to determine the delta when keys are updated. In the Trie, each node maintains score. During insert, add delta = val - map[key] to every node along the path from root. For sum(prefix), navigate to the prefix node and directly return curr.score in O(Prefix) time.

When to apply: Standard optimal solution for high-throughput prefix aggregation systems.

Algorithm

  1. Step 1: Maintain map<string, int> keyVals.
  2. Step 2: delta = val - (keyVals.count(key) ? keyVals[key] : 0). Update keyVals[key] = val.
  3. Step 3: insert(key, val): for each char in key, create child if missing, move to child, and add curr.score += delta.
  4. Step 4: sum(prefix): walk Trie for prefix characters. If any child is null, return 0.
  5. Step 5: Return curr.score immediately.

Interactive Trace for MapSum Delta Propagation

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: insert('apple', 3)
Visual state
Values and pointers at this exact step
tree
Root
score: 3
char 'a'
score: 3
char 'p'
score: 3

Node order shown; add connections to display explicit tree edges.

curr: p
Check / comparison
delta = 3 - 0 = 3
Decision / next transition
Node 'p' at level 2 has score = 3.
Why this step matters

Step 1: insert(apple, 3). Key apple is new, delta = 3. Update score += 3 on all nodes down path.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 int score;
9 TrieNode() : score(0) {
10 for (int i = 0; i < 26; i++) children[i] = nullptr;
11 }
12};
13
14class MapSum {
15 TrieNode* root;
16 unordered_map<string, int> keyVals;
17
18public:
19 MapSum() {
20 root = new TrieNode();
21 }
22
23 void insert(string key, int val) {
24 int delta = val - (keyVals.count(key) ? keyVals[key] : 0);
25 keyVals[key] = val;
26
27 TrieNode* curr = root;
28 for (char c : key) {
29 int idx = c - 'a';
30 if (!curr->children[idx]) {
31 curr->children[idx] = new TrieNode();
32 }
33 curr = curr->children[idx];
34 curr->score += delta;
35 }
36 }
37
38 int sum(string prefix) {
39 TrieNode* curr = root;
40 for (char c : prefix) {
41 int idx = c - 'a';
42 if (!curr->children[idx]) return 0;
43 curr = curr->children[idx];
44 }
45 return curr->score;
46 }
47};
48
49int main() {
50 MapSum mapSum;
51 mapSum.insert("apple", 3);
52 cout << "Optimal sum('ap'): " << mapSum.sum("ap") << endl;
53 mapSum.insert("app", 2);
54 cout << "Optimal sum('ap'): " << mapSum.sum("ap") << endl;
55 mapSum.insert("apple", 5); // override
56 cout << "Optimal sum('ap') after override: " << mapSum.sum("ap") << endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: insert: O(L), sum: O(Prefix) — Insertion walks L nodes, updating score in O(1). Sum walks Prefix characters and returns score in O(1).
  • Space complexity: O(Total characters * 26) — Trie nodes store children pointers and score integer.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map Key Scaninsert: O(1), sum: O(N * Prefix)O(N * L)Store pairs in a hash map. For sum(prefix), iterate all keys and add values of matching keys.Linear scan across all stored keys.
2.Better — Trie with Subtree DFS Summationinsert: O(L), sum: O(Prefix + Subtree Size)O(N * L * 26)Standard Trie storing val at terminal nodes. For sum, walk to prefix and run DFS summing all leaf values.Subtree traversal cost on each query.
3.Optimal — Trie with Precomputed Delta ScoresOptimalinsert: O(L), sum: O(Prefix)O(N * L * 26)Track delta = val - oldVal. Add delta to node.score along the path. sum returns node.score instantly in O(1) after reaching prefix.None. Instantaneous prefix aggregation.

Common Pitfalls & Crucial Edge Cases

Ignoring key override and always adding `val`

Corrupts prefix sums if a key is updated with a new value.

Traversing subtrees during `sum` queries

Takes O(Subtree size) instead of O(Prefix length) when delta scores can be precalculated.

Forgetting to update the hash map with the new value

Prevents subsequent overrides of the same key from calculating correct deltas.

Crucial Edge Cases to Validate:

  • Overriding key with new value — Delta propagation correctly adjusts scores: delta = val - oldVal.
  • Querying prefix that does not exist — Returns 0 immediately upon encountering null pointer.
  • Prefix is the exact key — Returns the aggregate score of all words having that key as a prefix (including the key itself).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the key design decision: calculating delta = val - oldVal allows O(Prefix) sum queries without subtree exploration.
  2. Explain the trade-off: using a hash map adds small memory overhead but makes both insert and sum strictly linear in string length.
  3. Mention that this pattern generalizes to any prefix-based aggregation (e.g. prefix frequency, prefix max, prefix weights).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is a secondary hash map used alongside the Trie in the optimal solution?

2.What is the time complexity of sum(prefix) in the optimal precomputed score approach?

Back to DSA Sheet