LeetCode 677 - Map Sum Pairs

The problem asks us to design a custom data structure that behaves like a map from strings to integers, while also supporting efficient prefix-based sum queries. There are two operations: 1. insert(key, val) This operation stores a string key with an integer value.

leetcodemediumhash-tablestringdesigntrie

LeetCode Problem 677

Difficulty: 🟡 Medium
Topics: Hash Table, String, Design, Trie

Solution

Problem Understanding

The problem asks us to design a custom data structure that behaves like a map from strings to integers, while also supporting efficient prefix-based sum queries.

There are two operations:

  1. insert(key, val)

This operation stores a string key with an integer value. If the key already exists, its old value must be replaced with the new value. 2. sum(prefix)

This operation returns the total sum of all values whose keys begin with the given prefix.

For example, if we insert:

  • "apple" -> 3
  • "app" -> 2

then calling sum("ap") should return 5, because both "apple" and "app" start with "ap".

The important detail is that keys can be overwritten. If "apple" was previously assigned 3 and later updated to 5, future prefix sums must reflect the new value rather than adding both values together.

The constraints are relatively small:

  • Key and prefix lengths are at most 50
  • At most 50 total operations

Even though the input size is small enough for simpler solutions to pass, the problem is fundamentally testing understanding of prefix-based data structures, especially tries.

A few important observations and edge cases immediately stand out:

  • Keys may be inserted multiple times, so we must correctly handle updates.
  • Prefixes may match zero keys, in which case the answer should be 0.
  • A prefix can itself be a full key while also matching longer keys.
  • Keys consist only of lowercase English letters, which makes trie-based implementations straightforward.
  • Prefix queries can overlap heavily, so recomputing sums repeatedly can become inefficient in larger-scale versions of the problem.

Approaches

Brute Force Approach

The simplest solution is to store every key-value pair in a hash map.

For insert, we simply update the dictionary entry:

map[key] = val

For sum(prefix), we iterate through every key in the dictionary and check whether the key starts with the given prefix. If it does, we add its value to the result.

This works because every stored key is explicitly examined during the prefix query, guaranteeing correctness.

However, the downside is that every sum operation requires scanning all keys. If the number of keys becomes large, repeated prefix queries become expensive.

Optimal Approach, Trie with Prefix Sums

The key insight is that prefix queries naturally align with a trie, also called a prefix tree.

A trie stores strings character by character. Every node represents a prefix. For example:

root
 └── a
      └── p
           └── p
                └── l
                     └── e

If we store, at each trie node, the total sum of all keys passing through that node, then answering a prefix query becomes extremely efficient.

For example:

  • The node representing "ap" stores the total value of all words beginning with "ap".
  • The node representing "app" stores the total value of all words beginning with "app".

Then:

  • insert updates sums along the traversal path
  • sum(prefix) simply walks to the prefix node and returns its stored total

The tricky part is handling updates correctly. Since keys can be overwritten, we must compute the difference:

delta = new_value - old_value

Then we add this delta to every trie node along the key's path.

Without this adjustment, repeated inserts of the same key would incorrectly accumulate values.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Insert: O(1), Sum: O(N × L) O(N × L) Scan all keys for every prefix query
Optimal Trie Insert: O(L), Sum: O(L) O(N × L) Stores prefix sums directly in trie nodes

Where:

  • N = number of keys
  • L = maximum string length

Algorithm Walkthrough

Optimal Trie Algorithm

  1. Create a trie node structure.

Each node stores:

  • A dictionary of child nodes
  • A running prefix sum

The prefix sum represents the total value of all keys passing through that node. 2. Maintain a separate hash map for exact key values.

This is necessary because keys can be updated. When inserting a key again, we need to know its previous value. 3. During insert(key, val), compute the value difference.

If the key already exists:

delta = val - old_value

Otherwise:

delta = val
  1. Update the stored key value in the hash map.

This ensures future updates use the latest value. 5. Traverse the trie character by character.

For each character:

  • Create the child node if it does not exist
  • Move to the child node
  • Add delta to that node's prefix sum

This propagates the value change to every relevant prefix. 6. During sum(prefix), traverse the trie using the prefix characters.

If at any point a character path does not exist, return 0. 7. After reaching the final prefix node, return its stored prefix sum.

Since every insertion updated this node correctly, the stored sum already represents the answer.

Why it works

The trie maintains the invariant that every node's stored sum equals the total value of all keys sharing that prefix.

When inserting a key, we propagate only the change in value, not the entire value. This guarantees that updates remain accurate even when keys are overwritten multiple times.

Therefore, when we reach the node corresponding to a prefix, its stored sum is exactly the total value of all matching keys.

Python Solution

class TrieNode:
    def __init__(self):
        self.children = {}
        self.prefix_sum = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()
        self.values = {}

    def insert(self, key: str, val: int) -> None:
        old_value = self.values.get(key, 0)
        delta = val - old_value

        self.values[key] = val

        current = self.root

        for char in key:
            if char not in current.children:
                current.children[char] = TrieNode()

            current = current.children[char]
            current.prefix_sum += delta

    def sum(self, prefix: str) -> int:
        current = self.root

        for char in prefix:
            if char not in current.children:
                return 0

            current = current.children[char]

        return current.prefix_sum

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

The implementation begins with a TrieNode class. Each node contains:

  • children, mapping characters to child nodes
  • prefix_sum, storing the sum of all keys sharing that prefix

Inside MapSum, we maintain:

  • root, the trie root
  • values, a dictionary storing the latest value for every key

The insert method first retrieves the old value of the key. This is critical because the problem allows overwriting existing keys.

We compute:

delta = new_value - old_value

This delta represents the amount by which all relevant prefix sums should change.

As we traverse the trie, we create missing nodes and add delta to each node's prefix_sum.

The sum method simply walks down the trie using the prefix characters. If the path exists, the final node already contains the desired total.

Go Solution

package main

type TrieNode struct {
	children  map[byte]*TrieNode
	prefixSum int
}

type MapSum struct {
	root   *TrieNode
	values map[string]int
}

func Constructor() MapSum {
	return MapSum{
		root: &TrieNode{
			children: make(map[byte]*TrieNode),
		},
		values: make(map[string]int),
	}
}

func (this *MapSum) Insert(key string, val int) {
	oldValue := this.values[key]
	delta := val - oldValue

	this.values[key] = val

	current := this.root

	for i := 0; i < len(key); i++ {
		char := key[i]

		if _, exists := current.children[char]; !exists {
			current.children[char] = &TrieNode{
				children: make(map[byte]*TrieNode),
			}
		}

		current = current.children[char]
		current.prefixSum += delta
	}
}

func (this *MapSum) Sum(prefix string) int {
	current := this.root

	for i := 0; i < len(prefix); i++ {
		char := prefix[i]

		if _, exists := current.children[char]; !exists {
			return 0
		}

		current = current.children[char]
	}

	return current.prefixSum
}

/**
 * Your MapSum object will be instantiated and called as such:
 * obj := Constructor()
 * obj.Insert(key, val)
 * param_2 := obj.Sum(prefix)
 */

The Go implementation follows the same logic as the Python version.

A few Go-specific details are worth noting:

  • Trie children are stored as map[byte]*TrieNode because the input only contains lowercase English letters.
  • Maps must be initialized using make.
  • Accessing a missing key in a Go map returns the zero value, which conveniently gives 0 for nonexistent previous key values.
  • Pointers are used for trie nodes to avoid unnecessary copying.

Worked Examples

Example 1

Operations:

insert("apple", 3)
sum("ap")
insert("app", 2)
sum("ap")

Step 1: insert("apple", 3)

delta = 3 - 0 = 3

Trie updates:

Prefix Stored Sum
a 3
ap 3
app 3
appl 3
apple 3

Stored values map:

Key Value
apple 3

Step 2: sum("ap")

Traverse:

root -> a -> p

Node "ap" stores:

3

Return:

3

Step 3: insert("app", 2)

delta = 2 - 0 = 2

Update trie:

Prefix Previous Sum New Sum
a 3 5
ap 3 5
app 3 5

Stored values map:

Key Value
apple 3
app 2

Step 4: sum("ap")

Traverse:

root -> a -> p

Node "ap" now stores:

5

Return:

5

Complexity Analysis

Measure Complexity Explanation
Time O(L) Both insert and sum traverse at most the string length
Space O(N × L) Trie may store every character of every key

Where:

  • N = number of inserted keys
  • L = maximum key length

The trie guarantees efficient prefix operations because each character is processed exactly once during traversal. The auxiliary hash map also provides constant-time access for overwrite handling.

The total trie size depends on how many unique prefixes exist across all inserted keys.

Test Cases

# Basic example from problem statement
obj = MapSum()
obj.insert("apple", 3)
assert obj.sum("ap") == 3  # single matching key

obj.insert("app", 2)
assert obj.sum("ap") == 5  # multiple matching keys

# Overwriting existing key
obj = MapSum()
obj.insert("apple", 3)
obj.insert("apple", 5)
assert obj.sum("apple") == 5  # old value replaced correctly

# Prefix with no matches
obj = MapSum()
obj.insert("apple", 3)
assert obj.sum("xyz") == 0  # nonexistent prefix

# Prefix equal to full key
obj = MapSum()
obj.insert("app", 2)
obj.insert("apple", 3)
assert obj.sum("app") == 5  # includes exact key and longer keys

# Multiple independent branches
obj = MapSum()
obj.insert("cat", 4)
obj.insert("car", 6)
obj.insert("dog", 5)

assert obj.sum("ca") == 10  # cat + car
assert obj.sum("do") == 5   # dog only
assert obj.sum("z") == 0    # no matches

# Repeated updates
obj = MapSum()
obj.insert("a", 1)
obj.insert("a", 2)
obj.insert("a", 10)

assert obj.sum("a") == 10  # latest value only

# Single character keys
obj = MapSum()
obj.insert("a", 1)
obj.insert("b", 2)

assert obj.sum("a") == 1
assert obj.sum("b") == 2

# Deep prefix chain
obj = MapSum()
obj.insert("a", 1)
obj.insert("ab", 2)
obj.insert("abc", 3)

assert obj.sum("a") == 6
assert obj.sum("ab") == 5
assert obj.sum("abc") == 3

Test Summary

Test Why
Basic example Verifies normal insertion and prefix summation
Overwriting existing key Ensures updates replace old values correctly
Prefix with no matches Confirms missing prefixes return 0
Prefix equal to full key Validates exact-key prefix handling
Multiple independent branches Tests trie branching correctness
Repeated updates Ensures delta logic works repeatedly
Single character keys Tests smallest valid key size
Deep prefix chain Validates nested prefix accumulation

Edge Cases

One important edge case is reinserting the same key with a different value. A naive implementation might simply add the new value again, causing prefix sums to become inflated over time. For example, inserting "apple" with 3 and later with 5 should result in a total contribution of 5, not 8. The implementation handles this by storing previous values and updating trie sums using only the difference between old and new values.

Another important case occurs when querying a prefix that does not exist in the trie. During traversal, the algorithm may encounter a missing child node before finishing the prefix. In that situation, the implementation immediately returns 0, because no stored keys can share a nonexistent prefix path.

A third subtle edge case happens when one key is itself a prefix of another key. For example:

"app"
"apple"

Both should contribute to sum("app"). The trie naturally handles this because every node stores cumulative sums for all descendant keys, not just keys ending at that node.

A final edge case involves very short keys and prefixes, especially length 1. Since the traversal logic works character by character regardless of string length, single-character inputs are handled identically to longer strings without any special-case code.