How hard is LeetCode 677. Map Sum Pairs?

LeetCode 677. Map Sum Pairs is rated Medium on LeetCode.

What is the time complexity of LeetCode 677. Map Sum Pairs?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 677. Map Sum Pairs?

The Python solution on this page uses O(n \times m \times C), where n and m are the number of keys and the maximum length of the keys, respectively; and C is the size of the character set, which is 26 in this problem auxiliary space.

What topics does LeetCode 677. Map Sum Pairs cover?

LeetCode 677. Map Sum Pairs is tagged Design, Trie, Hash Table and String on LeetCode.

Map Sum Pairs — LeetCode 677 Python Solution

MediumDesignTrieHash TableString

Problem: #677
Pattern: Trie
Reading time: 7 min
Source: leetcode.com

The problem

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.

Example

Input: ["MapSum", "insert", "sum", "insert", "sum"]
Output: [null, null, 3, null, 5]
Explanation: MapSum mapSum = new MapSum();

Python solution

Python

class Trie:
    def __init__(self):
        self.children: List[Trie | None] = [None] * 26
        self.val: int = 0

    def insert(self, w: str, x: int):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.val += x

    def search(self, w: str) -> int:
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return 0
            node = node.children[idx]
        return node.val


class MapSum:
    def __init__(self):
        self.d = defaultdict(int)
        self.tree = Trie()

    def insert(self, key: str, val: int) -> None:
        x = val - self.d[key]
        self.d[key] = val
        self.tree.insert(key, x)

    def sum(self, prefix: str) -> int:
        return self.tree.search(prefix)


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

Complexity

Measure	Complexity
Time	O(n)
Space	O(n \times m \times C), where n and m are the number of keys and the maximum length of the keys, respectively; and C is the size of the character set, which is 26 in this problem auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 677. Map Sum Pairs is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 677. Map Sum Pairs?: LeetCode 677. Map Sum Pairs is rated Medium on LeetCode.
What is the time complexity of LeetCode 677. Map Sum Pairs?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 677. Map Sum Pairs?: The Python solution on this page uses O(n \times m \times C), where n and m are the number of keys and the maximum length of the keys, respectively; and C is the size of the character set, which is 26 in this problem auxiliary space.
What topics does LeetCode 677. Map Sum Pairs cover?: LeetCode 677. Map Sum Pairs is tagged Design, Trie, Hash Table and String on LeetCode.