Watch 10 video solutions for Map Sum Pairs, a medium level problem involving Hash Table, String, Design. This walkthrough by Hua Hua has 3,945 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a map that allows you to do the following:
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-value pair will be overridden to the new one.int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
Constraints:
1 <= key.length, prefix.length <= 50key and prefix consist of only lowercase English letters.1 <= val <= 100050 calls will be made to insert and sum.Problem Overview: Design a data structure that supports two operations: insert(key, val) and sum(prefix). The structure stores string keys with integer values, and sum(prefix) must return the total value of all keys that start with the given prefix.
Approach 1: Using HashMap (Insert O(1), Sum O(n * k))
Store every key-value pair in a HashMap. The insert operation simply updates the map entry for the key. For the sum(prefix) query, iterate through all keys in the map and check whether each key starts with the given prefix using a string comparison. If it does, add its value to the running total.
This approach is straightforward and works well when the number of keys is small. However, every sum call scans all stored keys, making it inefficient for large datasets or frequent queries. The time complexity of sum becomes O(n * k), where n is the number of keys and k is the prefix length. The space complexity is O(n * k) for storing the strings in the map. This method relies on a Hash Table and simple String operations.
Approach 2: Using Trie (Insert O(k), Sum O(k))
A more efficient design uses a Trie where each node represents a prefix. Each node stores the cumulative sum of values for all keys passing through that prefix. During insert, compute the difference between the new value and the previous value of the key (tracked in a hash map). Traverse the trie character by character and update the prefix sums along the path.
For the sum(prefix) operation, simply traverse the trie using the prefix characters. Once the traversal reaches the final prefix node, return its stored cumulative value. Because the traversal only depends on the prefix length, both insert and sum run in O(k) time where k is the key or prefix length. Space complexity is O(n * k) for the trie nodes.
This approach is the standard solution for prefix aggregation problems and demonstrates efficient use of a Trie. It avoids repeatedly scanning all stored keys and scales well when the number of keys grows.
Recommended for interviews: The Trie-based solution is usually what interviewers expect for this problem. It shows that you recognize the prefix-query pattern and know how to maintain aggregated values in a trie. The HashMap solution demonstrates baseline problem understanding, but the Trie approach highlights stronger data structure design skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap with prefix scan | Insert: O(1), Sum: O(n * k) | O(n * k) | Simple implementation when the dataset is small or prefix queries are rare |
| Trie with prefix sums | Insert: O(k), Sum: O(k) | O(n * k) | Best for frequent prefix queries and large key sets |