Coding Interview PatternsMap Sum Pairs
MediumTrie

Map Sum Pairs

Explanation & Solution

Practice Problem

Description

Design a MapSum class that supports two operations:

  • insert(key, val) — Insert the key-value pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
  • sum(prefix) — Return the sum of all the values of keys that have a prefix equal to a given prefix.

Implement the MapSum class using a trie data structure.

Input:operations = ["MapSum","insert","sum","insert","sum"], operands = [[],["apple",3],["ap"],["app",2],["ap"]]
0
MapSum
1
insert
2
sum
3
insert
4
sum
Output:[null,null,3,null,5]
0
null
1
null
2
3
3
null
4
5

Explanation:

  • MapSum() — Initialize the object.
  • insert("apple", 3) — Insert key "apple" with val 3.
  • sum("ap") — Return 3 (apple = 3).
  • insert("app", 2) — Insert key "app" with val 2.
  • sum("ap") — Return 5 (apple = 3 + app = 2).

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

Approach

Trie pattern

1. Build a Trie with Prefix Sums

  • Create a TrieNode class with children (map of child nodes) and val (cumulative sum of all keys passing through this node)
  • Maintain a separate HashMap to store the current value of each key for handling overrides

2. Insert Operation

  • When inserting (key, val), compute delta = val - previousVal (previous value is 0 if key is new)
  • Traverse the trie character by character, creating nodes as needed
  • Add delta to each node's val along the path
  • Update the HashMap with the new value for the key

3. Sum Operation

  • Traverse the trie following the characters of the prefix
  • If any character is missing, return 0
  • Otherwise, the val at the last node of the prefix path is the answer — it already stores the cumulative sum of all keys with that prefix

4. Process All Operations

  • Iterate through the operations array, dispatching each to the appropriate handler
  • Collect results: null for constructor and insert, the sum value for sum queries

Key Insight

  • By storing prefix sums in each trie node and using a delta approach for updates, both insert and sum run in O(k) time where k is the key/prefix length
  • The delta technique correctly handles key overrides without needing to recompute sums

Solution Code

Previous
Longest Word in Dictionary
Next
Search Suggestions System