We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Map Sum Pairs

Number: 677

Difficulty: Medium

Paid? No

Companies: Amazon, Akuna Capital

Problem Description

Design a data structure that supports inserting a string key with an integer value and returning the sum of all values for keys that share a given prefix. If a key is inserted again, its value should be updated to the new one.

Key Insights

  • A brute-force solution iterates through all keys on every sum query, which is acceptable given the small constraints (max 50 calls).
  • A Trie (prefix tree) data structure can optimize the sum query by aggregating prefix sums along the insertion path.
  • When updating an existing key, the difference between the new value and the old value must be propagated through the Trie.
  • Maintaining a hashmap for tracking the current value of each key simplifies handling duplicate key insertions.

Space and Time Complexity

Time Complexity:

  • Insert: O(L) per key, where L is the length of the key.
  • Sum: O(P) per query, where P is the length of the prefix. Space Complexity:
  • O(N * L) in worst-case, where N is the number of keys and L is the average length of the keys.

Solution

We use a combination of a Trie and a HashMap. The HashMap will store the current value for each key to determine the delta when a key is updated. The Trie will store cumulative sums at each node such that each node represents a character in the keys. For insertion, we calculate the difference (delta) between the new value and the current value (if the key exists) and propagate this delta along the path of nodes in the Trie corresponding to the key. For sum query, we traverse the Trie using the prefix and return the stored cumulative sum at the node corresponding to the last character of the prefix. This approach efficiently handles prefix sum queries and dynamic updates.

Code Solutions

class TrieNode:
    def __init__(self):
        # dictionary to hold child nodes
        self.children = {}
        # cumulative sum for keys passing through this node
        self.sum = 0
        
class MapSum:
    def __init__(self):
        # root node of Trie
        self.root = TrieNode()
        # dictionary to store the current value of inserted keys
        self.keyMap = {}
    
    def insert(self, key: str, val: int) -> None:
        # calculate delta value for update
        delta = val - self.keyMap.get(key, 0)
        # update the keyMap with new value
        self.keyMap[key] = val
        # traverse the Trie and update the cumulative sum at each node along the key's path
        current = self.root
        current.sum += delta
        for ch in key:
            if ch not in current.children:
                current.children[ch] = TrieNode()
            current = current.children[ch]
            current.sum += delta

    def sum(self, prefix: str) -> int:
        # traverse the Trie following the prefix
        current = self.root
        for ch in prefix:
            if ch not in current.children:
                return 0
            current = current.children[ch]
        return current.sum

# Example usage:
# mapSum = MapSum()
# mapSum.insert("apple", 3)
# print(mapSum.sum("ap"))  # Output: 3
# mapSum.insert("app", 2)
# print(mapSum.sum("ap"))  # Output: 5
← Back to All Questions