grid47 Exploring patterns and algorithms
Aug 31, 2024
8 min read
Solution to LeetCode 677: Map Sum Pairs Problem
Design a map-like data structure that supports key-value insertion and sum queries for keys starting with a specific prefix.
Problem
Approach
Steps
Complexity
Input: The input consists of a series of operations on the MapSum object. You will be given a list of operations, where each operation can either insert a key-value pair into the map or request the sum of values for a given prefix.
Example: ["apple", 3], ["ap"]
Constraints:
• 1 <= key.length, prefix.length <= 50
• key and prefix consist only of lowercase English letters.
• 1 <= val <= 1000
• At most 50 calls will be made to insert and sum.
Output: The output for each operation will be either null (for insert operations) or the result of a sum operation.
Example: 3, 5
Constraints:
• The output for insert operations is always null.
• The sum operation returns an integer value.
Goal: Efficiently handle insertions and prefix sum queries by storing keys and their corresponding values.
Steps:
• 1. For insertions, store key-value pairs in a map-like structure.
• 2. For sum queries, efficiently search for all keys starting with the given prefix and sum their values.
Goal: The constraints ensure that the problem remains manageable within time and space limits, even with multiple insert and sum operations.
Steps:
• The maximum number of insertions and sum queries is 50.
Assumptions:
• The map structure will be used efficiently with respect to the number of insertions and sum queries.
• Input: ["apple", 3], ["ap"]
• Explanation: In this example, the sum of keys starting with 'ap' is just 3 because 'apple' is the only key in the map that starts with 'ap'.
• Input: ["apple", 3], ["app", 2], ["ap"]
• Explanation: After inserting 'app' with value 2, the sum of keys starting with 'ap' is 5, which is the sum of 'apple' (3) and 'app' (2).
Approach: To implement this map-like structure, we will use a trie to store keys and their cumulative values. This allows us to efficiently compute the sum of all values with a given prefix.
Observations:
• Trie structures are well-suited for operations involving prefixes.
• We can store each key in the trie, while maintaining cumulative sums along each path to efficiently compute prefix sums.
Steps:
• 1. Implement a trie where each node stores the sum of values for all keys that pass through it.
• 2. For insertion, traverse the trie and update the sum at each node along the path of the key.
• 3. For sum queries, traverse the trie to find the sum of all values that match the given prefix.
Empty Inputs:
• If there are no insertions, a sum query should return 0.
Large Inputs:
• With a large number of insertions and sum queries, the trie structure will help ensure that the operations remain efficient.
Special Values:
• Handle the case where multiple insertions for the same key should overwrite the previous value.
Constraints:
• Ensure that the trie is efficiently implemented to handle up to 50 insert and sum operations.
int sum =0;
string s;
public:TrieNode() {
s ="";
sum =0;
next.resize(26, NULL);
}
voidadd(string key, int val) {
TrieNode* root =this;
for(int i =0; i < key.size(); i++) {
int idx = key[i] -'a';
if(root->next[idx] ==NULL)
root->next[idx] =new TrieNode();
root = root->next[idx];
root->sum += val;
}
root->s = key;
}
intval(string key) {
TrieNode* root =this;
for(int i =0; i < key.size(); i++) {
int idx = key[i] -'a';
if(root->next[idx] ==NULL)
return0;
root = root->next[idx];
}
return root->sum;
}
};
classMapSum {
TrieNode* root;
map<string, int> store;
public:MapSum() {
root =new TrieNode();
}
voidinsert(string key, int val) {
int x = val;
if(store[key] >0)
val = val - store[key];
root->add(key, val);
store[key] = x;
}
intsum(string prefix) {
return root->val(prefix);
}
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum* obj = new MapSum();
* obj->insert(key,val);
* int param_2 = obj->sum(prefix);
1 : Variable Initialization
int sum =0;
Initialize a variable to store the sum of values for keys stored in the trie.
2 : Variable Initialization
string s;
Initialize a string variable to store the key in the TrieNode.
3 : Access Control
public:
This section defines public methods for the class.
4 : Constructor
TrieNode() {
Constructor to initialize a TrieNode with default values: an empty string and sum set to zero.
5 : Assignment
s ="";
Assign an empty string to the string variable s in the TrieNode.
6 : Assignment
sum =0;
Assign zero to the sum variable to initialize it.
7 : Container Initialization
next.resize(26, NULL);
Resize the next container (a vector of TrieNode pointers) to hold 26 elements, each initialized to NULL, representing the 26 letters of the alphabet.
8 : Method Definition
voidadd(string key, int val) {
Define the 'add' method to insert a key and its associated value into the trie.
9 : Pointer Initialization
TrieNode* root =this;
Initialize a pointer root to point to the current TrieNode instance.
10 : Loop
for(int i =0; i < key.size(); i++) {
Iterate over each character in the given key.
11 : Index Calculation
int idx = key[i] -'a';
Calculate the index corresponding to the current character in the key.
12 : Condition
if(root->next[idx] ==NULL)
Check if the trie node corresponding to the current character does not exist.
13 : Pointer Initialization
root->next[idx] =new TrieNode();
If the trie node does not exist, create a new TrieNode and assign it to the corresponding position in the next array.
14 : Pointer Update
root = root->next[idx];
Move the root pointer to the next trie node.
15 : Sum Update
root->sum += val;
Add the value to the sum of the current trie node.
16 : Assignment
root->s = key;
Assign the key to the string variable s in the final trie node.
17 : Method Definition
intval(string key) {
Define the 'val' method to retrieve the sum of values for the given key.
18 : Pointer Initialization
TrieNode* root =this;
Initialize a pointer root to point to the current TrieNode instance.
19 : Loop
for(int i =0; i < key.size(); i++) {
Iterate over each character in the given key.
20 : Index Calculation
int idx = key[i] -'a';
Calculate the index corresponding to the current character in the key.
21 : Condition
if(root->next[idx] ==NULL)
Check if the trie node corresponding to the current character does not exist.
22 : Return
return0;
Return 0 if the trie node does not exist, meaning the key is not in the trie.
23 : Pointer Update
root = root->next[idx];
Move the root pointer to the next trie node.
24 : Return
return root->sum;
Return the sum of values for the given key.
25 : Class Definition
classMapSum {
Define the MapSum class, which uses a TrieNode to implement the insert and sum operations.
26 : Pointer Initialization
TrieNode* root;
Initialize a pointer root to point to a TrieNode.
27 : Container Initialization
map<string, int> store;
Initialize a map to store the key-value pairs.
28 : Constructor
public:MapSum() {
Define the constructor for MapSum, which initializes the root pointer to a new TrieNode.
29 : Pointer Initialization
root =new TrieNode();
Initialize the root pointer to a new TrieNode.
30 : Method Definition
voidinsert(string key, int val) {
Define the 'insert' method to insert a key-value pair into the map and trie.
31 : Value Adjustment
int x = val;
Store the current value of the key.
32 : Condition
if(store[key] >0)
Check if the key is already in the map and adjust the value.
33 : Value Update
val = val - store[key];
Adjust the new value by subtracting the old value.
34 : Method Call
root->add(key, val);
Call the 'add' method of TrieNode to insert the key-value pair into the trie.
35 : Map Update
store[key] = x;
Update the map with the new value for the key.
36 : Method Definition
intsum(string prefix) {
Define the 'sum' method to calculate the sum of values for all keys starting with the given prefix.
37 : Method Call
return root->val(prefix);
Call the 'val' method of TrieNode to get the sum for the given prefix.
Best Case: O(k) where k is the length of the key or prefix.
Average Case: O(k) where k is the length of the key or prefix.
Worst Case: O(k) where k is the length of the key or prefix.
Description: Both insert and sum operations take O(k) time, where k is the length of the key or prefix.
Best Case: O(n * k) where n is the number of keys and k is the length of the keys.
Worst Case: O(n * k) where n is the number of keys and k is the length of the keys.
Description: The space complexity depends on the number of keys and their lengths, as each key and its associated value are stored in the trie.
