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.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.
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.
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.
| Approach | Complexity |
|---|---|
| Approach 1: Using HashMap | Time Complexity: |
| Approach 2: Using Trie | Time Complexity: |
Leetcode - Max Number of K-Sum Pairs (Python) • Timothy H Chang • 8,391 views views
Watch 9 more video solutions →Practice Map Sum Pairs with our built-in code editor and test cases.
Practice on FleetCode