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.
Using HashMap
This approach uses two hash maps. The first map stores the keys and their respective values, while the second map, usually called the prefix map, is used to cache the sums of prefixes. Every time a key-value pair is inserted, we iteratively update the sums of all prefixes for that key. In this approach, every insert operation might take time proportional to the length of the key, and the sum operation is almost constant time thanks to the prefix sums map.
The code defines a MapSum class with a constructor initializing two dictionaries: one to store the map of key-value pairs, and the second to store prefix sums. The insert method calculates the change in value for a key and updates the prefix sums accordingly. The sum method retrieves the sum for a given prefix from the prefix map.
Python
Java
C++
C#
JavaScript
Time Complexity: O(k) for insert, where k is the length of the key. O(1) for sum.
Space Complexity: O(n), where n is the number of keys stored.
Using Trie
This approach involves using a Trie (Prefix Tree) for storing keys. Along with each node of the Trie, maintain a map that stores prefix sum. Every time a key is inserted, traverse each node and update the corresponding prefix sum. When retrieving a sum for a given prefix, traverse the Trie up to the end of the prefix and return the stored prefix sum.
In this Python code, we define a TrieNode class to represent each node in the Trie, including children nodes and value for prefix sum. The MapSum class utilizes these TrieNodes for insertion and sum retrieval. The insert method updates the Trie structure with deltas, and the sum method traverses the Trie for the prefix to get the sum.
Python
Java
C++
C#
JavaScript
Time Complexity: O(k) for insert and O(p) for sum, where k is the length of the key and p is the length of the prefix.
Space Complexity: O(n), where n is the number of keys stored in the Trie.
We use a hash table d to store key-value pairs and a trie t to store the prefix sums of the key-value pairs. Each node in the trie contains two pieces of information:
val: the total sum of the values of the key-value pairs with this node as the prefixchildren: an array of length 26 that stores the child nodes of this nodeWhen inserting a key-value pair (key, val), we first check if the key exists in the hash table. If it does, the val of each node in the trie needs to subtract the original value of the key and then add the new value. If it does not exist, the val of each node in the trie needs to add the new value.
When querying the prefix sum, we start from the root node of the trie and traverse the prefix string. If the current node's child nodes do not contain the character, it means the prefix does not exist in the trie, and we return 0. Otherwise, we continue to traverse the next character until we finish traversing the prefix string and return the val of the current node.
In terms of time complexity, the time complexity of inserting a key-value pair is O(n), where n is the length of the key. The time complexity of querying the prefix sum is O(m), where m is the length of the prefix.
The space complexity is O(n times m times C), where n and m are the number of keys and the maximum length of the keys, respectively; and C is the size of the character set, which is 26 in this problem.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| Approach | Complexity |
|---|---|
| Approach 1: Using HashMap | Time Complexity: |
| Approach 2: Using Trie | Time Complexity: |
| Hash Table + Trie | — |
| 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 |
花花酱 LeetCode 677. Map Sum Pairs - 刷题找工作 EP61 • Hua Hua • 3,945 views views
Watch 9 more video solutions →Practice Map Sum Pairs with our built-in code editor and test cases.
Practice on FleetCode