677. Map Sum Pairs


Implement a MapSum class with insert, and sum methods.

For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example 1:

Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5


Approach #1: Brute Force [Accepted]

Intuition and Algorithm

For each key in the map, if that key starts with the given prefix, then add it to the answer.

Complexity Analysis

  • Time Complexity: Every insert operation is . Every sum operation is where is the number of items in the map, and is the length of the input prefix.

  • Space Complexity: The space used by map is linear in the size of all input key and val values combined.

Approach #2: Prefix Hashmap [Accepted]

Intuition and Algorithm

We can remember the answer for all possible prefixes in a HashMap score. When we get a new (key, val) pair, we update every prefix of key appropriately: each prefix will be changed by delta = val - map[key], where map is the previous associated value of key (zero if undefined.)

Complexity Analysis

  • Time Complexity: Every insert operation is , where is the length of the key, as strings are made of an average length of . Every sum operation is .

  • Space Complexity: The space used by map and score is linear in the size of all input key and val values combined.

Approach #3: Trie [Accepted]

Intuition and Algorithm

Since we are dealing with prefixes, a Trie (prefix tree) is a natural data structure to approach this problem. For every node of the trie corresponding to some prefix, we will remember the desired answer (score) and store it at this node. As in Approach #2, this involves modifying each node by delta = val - map[key].

Complexity Analysis

  • Time Complexity: Every insert operation is , where is the length of the key. Every sum operation is .

  • Space Complexity: The space used is linear in the size of the total input.

Analysis written by: @awice

Submit Solution