Sponsored
Sponsored
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.
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.
1import java.util.HashMap;
2
3class MapSum {
4 HashMap<String, Integer> map;
5 HashMap<String, Integer> prefixMap;
6
7 public MapSum() {
8 map = new HashMap<>();
9 prefixMap = new HashMap<>();
10 }
11
12 public void insert(String key, int val) {
13 int delta = val - map.getOrDefault(key, 0);
14 map.put(key, val);
15 for (int i = 1; i <= key.length(); i++) {
16 String prefix = key.substring(0, i);
17 prefixMap.put(prefix, prefixMap.getOrDefault(prefix, 0) + delta);
18 }
19 }
20
21 public int sum(String prefix) {
22 return prefixMap.getOrDefault(prefix, 0);
23 }
24}In Java, the MapSum class uses two HashMaps similar to the Python solution. The key delta is used to update the key's value and the prefix sums. The insert and sum methods handle the logic for updates and retrieval respectively.
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.
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.
1
public class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public int Value = 0;
}
public class MapSum {
private TrieNode root;
private Dictionary<string, int> map;
public MapSum() {
root = new TrieNode();
map = new Dictionary<string, int>();
}
public void Insert(string key, int val) {
int delta = val - (map.ContainsKey(key) ? map[key] : 0);
map[key] = val;
TrieNode node = root;
foreach (char c in key) {
if (!node.Children.ContainsKey(c)) {
node.Children[c] = new TrieNode();
}
node = node.Children[c];
node.Value += delta;
}
}
public int Sum(string prefix) {
TrieNode node = root;
foreach (char c in prefix) {
if (!node.Children.ContainsKey(c)) return 0;
node = node.Children[c];
}
return node.Value;
}
}C#'s solution mirrors the structure of other languages, using dictionaries to manage children nodes within a Trie and updating sums as keys are added. The logic for insert and sum aligns with Trie traversals updated with prefixes.