#677

Medium

LeetCode Problem Workspace

Map Sum Pairs

Design and implement a data structure that supports efficient insertion and sum queries based on string prefixes.

Problem Statement

Implement a MapSum class that supports two main operations: inserting a key-value pair and calculating the sum of all values associated with keys that have a given prefix. The insert method should store the key-value pairs, and the sum method should return the total value of all keys starting with a specific prefix.

You need to handle the insert and sum operations efficiently, making use of appropriate data structures that allow fast prefix lookups and value aggregation. The key length and prefix length will not exceed 50, and the number of operations will be capped at 50, so your solution should scale well under these constraints.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Use of Hash Table

The key-value pairs are stored in a hash table, allowing constant time complexity for both insert and lookup operations. The hash table maps the string keys to their corresponding values, making insertions straightforward.

Efficient Prefix Sum Calculation

To calculate the sum of all keys starting with a given prefix, you can use a trie-like structure, where each node represents a character. By traversing the trie based on the given prefix, you can quickly gather the sum of all matching keys.

Handling Updates and Prefix Queries

Whenever a key is inserted or updated, you need to adjust the sum of the values stored in the trie nodes. This ensures that sum queries return accurate results after each modification, making the solution dynamic and responsive.

Complexity Analysis

Metric	Value
Time	Every insert operation is
Space	The space used is linear in the size of the total input

The time complexity for each insert operation is O(n), where n is the length of the key being inserted, because you may need to traverse the key's characters. The sum operation takes O(p), where p is the length of the prefix, as you only traverse the trie nodes corresponding to the prefix. The space complexity is O(m), where m is the total number of characters in all inserted keys, since they are stored in the hash table and trie structure.

What Interviewers Usually Probe

Can the candidate design efficient insert and sum methods?
Does the candidate understand the trade-offs between hash tables and trie structures for prefix-based queries?
How well does the candidate handle updates to the data structure and ensure consistent results in subsequent queries?

Common Pitfalls or Variants

Common pitfalls

Not considering how to handle key updates efficiently, potentially leading to incorrect sum results.
Inefficient prefix sum calculation that doesn't leverage a trie structure, resulting in suboptimal performance.
Mismanagement of space, such as storing redundant data in the trie, leading to higher than necessary memory usage.

Follow-up variants

Extend the MapSum class to support deletion of key-value pairs.
Implement a version of MapSum that supports case-sensitive strings.
Optimize the solution to handle more than 50 operations efficiently, focusing on scaling.

FAQ

How does MapSum handle key updates?

When a key is updated in MapSum, the value is adjusted in both the hash table and the trie, ensuring the sum queries return accurate results.

What is the time complexity of the sum operation?

The sum operation runs in O(p), where p is the length of the prefix, as it only needs to traverse the trie nodes corresponding to the given prefix.

How do you optimize MapSum for multiple sum operations?

To optimize for multiple sum operations, you can ensure the trie structure is efficient by storing cumulative sums at each node, avoiding repeated work during subsequent queries.

What is the space complexity of MapSum?

The space complexity is O(m), where m is the total number of characters in all the inserted keys, as the keys are stored in the hash table and trie.

Can MapSum be extended to support key deletions?

Yes, MapSum can be extended to support key deletions by removing keys from both the hash table and trie, ensuring sum operations are correctly updated afterward.

terminal

Solution

Solution 1: Hash Table + Trie

We use a hash table $d$ to store key-value pairs and a trie $t$ to store the prefix sums of the key-value pairs. Each node in the trie contains two pieces of information:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

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)

Continue Practicing

#676 implement magic dictionary #745 prefix and suffix search #208 implement trie prefix tree