Introduction

In this blog post, we will explore how to solve the LeetCode problem "677" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Design a map that allows you to do the following: Maps a string key to a given value. Returns the sum of the values that have a key with a prefix equal to a given string. 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 <= 50 key and prefix consist of only lowercase English letters. 1 <= val <= 1000 At most 50 calls will be made to insert and sum.

Explanation

Here's a solution to the MapSum problem:

• Trie Data Structure: Utilize a Trie (prefix tree) to efficiently store the keys and their corresponding values. Each node in the Trie represents a character, and paths from the root to a node represent prefixes/keys.

• Value Aggregation: Store the value associated with each key directly at the terminal node representing the key. Additionally, at each node of the Trie, store the sum of all values in the subtree rooted at that node. This allows for O(prefix length) sum calculation.

• Efficient insert operation: In the insert operation, we traverse the Trie based on the key. If the key already exists, subtract the old value from the subtree sums along the path and add the new value.

• Runtime and Storage Complexity:

  • Runtime: insert: O(K), sum: O(P), where K is the length of the key and P is the length of the prefix.
  • Storage: O(N * L), where N is the number of inserted keys, and L is the average length of the keys.

Code

    class TrieNode:
    def __init__(self):
        self.children = {}
        self.value = 0
        self.subtree_sum = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()
        self.key_map = {}  # Store key-value pairs for efficient updates

    def insert(self, key: str, val: int) -> None:
        node = self.root
        delta = val - self.key_map.get(key, 0)  # Calculate the change in value
        self.key_map[key] = val  # Update the value in the map

        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.subtree_sum += delta  # Update subtree sums along the path
        node.value = val

    def sum(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.subtree_sum


# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)