Map Sum Pairs - Solution & Explanation

Q: Is Map Sum Pairs easy or hard?

Map Sum Pairs is rated Medium difficulty. The challenge comes from designing a data structure that efficiently supports prefix sum queries. Recognizing the Trie pattern and maintaining prefix aggregates is the key insight.

Q: How to solve Map Sum Pairs in O(k)?

Use a Trie that stores prefix sums at each node. During insertion, compute the value difference from the previous key value and update every node along the path. For the sum operation, traverse the trie using the prefix and return the stored sum at the final node.

Q: What is the best approach for Map Sum Pairs?

The Trie-based approach is the most efficient solution. Each node in the trie stores the cumulative value of all keys sharing that prefix. Both insert and sum operations run in O(k) time, where k is the key or prefix length, making it significantly faster than scanning all keys.

Q: What data structure is used in Map Sum Pairs?

The optimal solution uses a Trie combined with a HashMap. The HashMap tracks previous key values so updates can adjust prefix sums correctly, while the Trie enables fast prefix traversal for the sum operation.

Q: What is the time complexity of Map Sum Pairs?

Using a HashMap with prefix scanning gives O(1) insert time but O(n * k) time for each sum query. The optimized Trie solution performs both insert and sum operations in O(k) time, where k is the length of the key or prefix.

Q: Map Sum Pairs Python or Java solution approach?

In Python or Java, implement a Trie node with a dictionary or array of children and store a running prefix sum at each node. Maintain a separate HashMap for key values to compute delta updates during insert operations.

Q: Is Map Sum Pairs asked at Google, Amazon, or Meta?

Map Sum Pairs is a common design-style interview problem involving prefix queries and tries. Variations of prefix aggregation and trie-based data structures have appeared in interviews at companies like Google, Amazon, and Meta.

MediumHash Table String Design Trie30 min readAsked at: Google, Flipkart, Akuna Capital

Practice this problem

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.

Approach Overview

Problem Overview: Design a data structure that supports two operations: insert(key, val) and sum(prefix). The structure stores string keys with integer values, and sum(prefix) must return the total value of all keys that start with the given prefix.

Approach 1: Using HashMap (Insert O(1), Sum O(n * k))

Store every key-value pair in a HashMap. The insert operation simply updates the map entry for the key. For the sum(prefix) query, iterate through all keys in the map and check whether each key starts with the given prefix using a string comparison. If it does, add its value to the running total.

This approach is straightforward and works well when the number of keys is small. However, every sum call scans all stored keys, making it inefficient for large datasets or frequent queries. The time complexity of sum becomes O(n * k), where n is the number of keys and k is the prefix length. The space complexity is O(n * k) for storing the strings in the map. This method relies on a Hash Table and simple String operations.

Approach 2: Using Trie (Insert O(k), Sum O(k))

A more efficient design uses a Trie where each node represents a prefix. Each node stores the cumulative sum of values for all keys passing through that prefix. During insert, compute the difference between the new value and the previous value of the key (tracked in a hash map). Traverse the trie character by character and update the prefix sums along the path.

For the sum(prefix) operation, simply traverse the trie using the prefix characters. Once the traversal reaches the final prefix node, return its stored cumulative value. Because the traversal only depends on the prefix length, both insert and sum run in O(k) time where k is the key or prefix length. Space complexity is O(n * k) for the trie nodes.

This approach is the standard solution for prefix aggregation problems and demonstrates efficient use of a Trie. It avoids repeatedly scanning all stored keys and scales well when the number of keys grows.

Recommended for interviews: The Trie-based solution is usually what interviewers expect for this problem. It shows that you recognize the prefix-query pattern and know how to maintain aggregated values in a trie. The HashMap solution demonstrates baseline problem understanding, but the Trie approach highlights stronger data structure design skills.

Approach 1: Approach 1: Using HashMap

Using HashMap

This approach uses two hash maps. The first map stores the keys and their respective values, while the second map, usually called the prefix map, is used to cache the sums of prefixes. Every time a key-value pair is inserted, we iteratively update the sums of all prefixes for that key. In this approach, every insert operation might take time proportional to the length of the key, and the sum operation is almost constant time thanks to the prefix sums map.

The code defines a MapSum class with a constructor initializing two dictionaries: one to store the map of key-value pairs, and the second to store prefix sums. The insert method calculates the change in value for a key and updates the prefix sums accordingly. The sum method retrieves the sum for a given prefix from the prefix map.

Code

Python Java C++C#JavaScript

Python

Java

C++

JavaScript

Complexity

Time Complexity: O(k) for insert, where k is the length of the key. O(1) for sum.
Space Complexity: O(n), where n is the number of keys stored.

Try this approach in the editor →

Approach 2: Approach 2: Using Trie

Using Trie

This approach involves using a Trie (Prefix Tree) for storing keys. Along with each node of the Trie, maintain a map that stores prefix sum. Every time a key is inserted, traverse each node and update the corresponding prefix sum. When retrieving a sum for a given prefix, traverse the Trie up to the end of the prefix and return the stored prefix sum.

In this Python code, we define a TrieNode class to represent each node in the Trie, including children nodes and value for prefix sum. The MapSum class utilizes these TrieNodes for insertion and sum retrieval. The insert method updates the Trie structure with deltas, and the sum method traverses the Trie for the prefix to get the sum.

Code

Python Java C++C#JavaScript

Python

Java

C++

JavaScript

Complexity

Time Complexity: O(k) for insert and O(p) for sum, where k is the length of the key and p is the length of the prefix.
Space Complexity: O(n), where n is the number of keys stored in the Trie.

Try this approach in the editor →

Approach 3: 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:

val: the total sum of the values of the key-value pairs with this node as the prefix
children: an array of length 26 that stores the child nodes of this node

When inserting a key-value pair (key, val), we first check if the key exists in the hash table. If it does, the val of each node in the trie needs to subtract the original value of the key and then add the new value. If it does not exist, the val of each node in the trie needs to add the new value.

When querying the prefix sum, we start from the root node of the trie and traverse the prefix string. If the current node's child nodes do not contain the character, it means the prefix does not exist in the trie, and we return 0. Otherwise, we continue to traverse the next character until we finish traversing the prefix string and return the val of the current node.

In terms of time complexity, the time complexity of inserting a key-value pair is O(n), where n is the length of the key. The time complexity of querying the prefix sum is O(m), where m is the length of the prefix.

The space complexity is 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.

Code

Python Java C++Go TypeScript Rust JavaScript C#

Python

Java

C++

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Using HashMap	Time Complexity: `O(k)` for insert, where `k` is the length of the key. `O(1)` for sum. Space Complexity: `O(n)`, where `n` is the number of keys stored.
Approach 2: Using Trie	Time Complexity: `O(k)` for insert and `O(p)` for sum, where `k` is the length of the key and `p` is the length of the prefix. Space Complexity: `O(n)`, where `n` is the number of keys stored in the Trie.
Hash Table + Trie	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
HashMap with prefix scan	Insert: O(1), Sum: O(n * k)	O(n * k)	Simple implementation when the dataset is small or prefix queries are rare
Trie with prefix sums	Insert: O(k), Sum: O(k)	O(n * k)	Best for frequent prefix queries and large key sets

Video Solution

花花酱 LeetCode 677. Map Sum Pairs - 刷题找工作 EP61 • Hua Hua • 3,947 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Map Sum Pairs easy or hard?

Map Sum Pairs is rated Medium difficulty. The challenge comes from designing a data structure that efficiently supports prefix sum queries. Recognizing the Trie pattern and maintaining prefix aggregates is the key insight.

How to solve Map Sum Pairs in O(k)?

Use a Trie that stores prefix sums at each node. During insertion, compute the value difference from the previous key value and update every node along the path. For the sum operation, traverse the trie using the prefix and return the stored sum at the final node.

What is the best approach for Map Sum Pairs?

The Trie-based approach is the most efficient solution. Each node in the trie stores the cumulative value of all keys sharing that prefix. Both insert and sum operations run in O(k) time, where k is the key or prefix length, making it significantly faster than scanning all keys.

What data structure is used in Map Sum Pairs?

The optimal solution uses a Trie combined with a HashMap. The HashMap tracks previous key values so updates can adjust prefix sums correctly, while the Trie enables fast prefix traversal for the sum operation.

What is the time complexity of Map Sum Pairs?

Using a HashMap with prefix scanning gives O(1) insert time but O(n * k) time for each sum query. The optimized Trie solution performs both insert and sum operations in O(k) time, where k is the length of the key or prefix.

Map Sum Pairs Python or Java solution approach?

In Python or Java, implement a Trie node with a dictionary or array of children and store a running prefix sum at each node. Maintain a separate HashMap for key values to compute delta updates during insert operations.

Is Map Sum Pairs asked at Google, Amazon, or Meta?

Map Sum Pairs is a common design-style interview problem involving prefix queries and tries. Variations of prefix aggregation and trie-based data structures have appeared in interviews at companies like Google, Amazon, and Meta.

Ready to solve this problem?

Practice Map Sum Pairs with our built-in code editor and test cases.

Practice on FleetCode

Sort the Jumbled Numbers

Sum of Prefix Scores of Strings

Problem Info

DifficultyMedium

Acceptance57.4%

Approaches3

Reading time30 min

Asked at

Google Flipkart Akuna Capital

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Using HashMap

Code

Complexity

Approach 2: Approach 2: Using Trie

Code

Complexity

Approach 3: Hash Table + Trie

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents