LeetCode 677: Map Sum Pairs Solution in Python – A Step-by-Step Guide

Imagine you’re a word accountant managing a magical ledger where you can insert entries like "apple" with a value of 3 and "app" with a value of 2, and your task is to quickly sum the values of all entries starting with a prefix—like "ap," which totals 5. That’s the challenge of LeetCode 677: Map Sum Pairs, a medium-level problem that’s all about designing a data structure to track key-value pairs and compute prefix sums efficiently. Using Python, we’ll explore two solutions: the Best Solution, a trie with prefix sum for speed and elegance, and an Alternative Solution, a hash map with prefix iteration that’s simpler but slower. With detailed examples, beginner-friendly breakdowns—especially for the trie method—and clear code, this guide will help you tally those sums, whether you’re new to coding or leveling up. Let’s open that ledger and start summing!

What Is LeetCode 677: Map Sum Pairs?

In LeetCode 677: Map Sum Pairs, you need to implement a MapSum class with two main methods:

insert(key: str, val: int) -> None: Inserts a key-value pair into the map, overwriting if the key exists.
sum(prefix: str) -> int: Returns the sum of values for all keys that start with the given prefix.

For example, if you insert "apple" (3) and "app" (2), then sum("ap") returns 5 (3 + 2), and after inserting "apple" (5), sum("ap") updates to 7 (5 + 2). The problem tests your ability to design a data structure for efficient prefix-based value aggregation.

Problem Statement

Class: MapSum
Methods:

insert(key: str, val: int) -> None: Add or update key-value pair.
sum(prefix: str) -> int: Sum values of keys with prefix.

Rules:

Keys are lowercase English letters.
Overwrite value if key already exists.
Return sum of values for matching prefixes.

Constraints

1 ≤ key.length, prefix.length ≤ 10.
Keys and prefixes consist of lowercase English letters.
1 ≤ val ≤ 1000.
At most 50 calls to insert and sum.

Examples

Input:

["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output: [null, null, 3, null, 5]

insert("apple", 3): {"apple": 3}.
sum("ap"): 3 (only "apple").
insert("app", 2): {"apple": 3, "app": 2}.
sum("ap"): 5 (3 + 2).

Input:

["MapSum", "insert", "insert", "sum"]
[[], ["apple", 3], ["apple", 5], ["ap"]]

Output: [null, null, null, 5]

Overwrites "apple" to 5, sum = 5.

These examples set the map—let’s solve it!

Understanding the Problem: Summing Prefix Values

To solve LeetCode 677: Map Sum Pairs in Python, we need to implement a MapSum class that efficiently inserts key-value pairs and computes the sum of values for keys matching a prefix. A brute-force approach—storing pairs in a list and checking each key for prefix matches—would be O(n * l) per sum call (n = keys, l = length), reasonable for small constraints but slow for frequent calls. Since we’re dealing with prefixes, a trie or hash map can optimize this. We’ll use:

Best Solution (Trie with Prefix Sum): O(l) insert and sum time, O(n * l) space—fast and scalable.
Alternative Solution (Hash Map with Prefix Iteration): O(n l) insert and sum time, O(n l) space—simple but less efficient.

Let’s start with the trie solution, breaking it down for beginners.

Best Solution: Trie with Prefix Sum

Why This Is the Best Solution

The trie with prefix sum approach is the top choice for LeetCode 677 because it’s efficient—O(l) time for both insert and sum with O(n * l) space—and uses a trie (prefix tree) where each node stores the sum of values for all words passing through it, allowing quick prefix sum retrieval. It fits constraints (n ≤ 50, l ≤ 10) perfectly and is intuitive once you see the trie structure. It’s like planting a word tree where every branch knows the sum of its fruits!

How It Works

Think of this as a prefix accountant:

Step 1: Define Trie Node:

Each node has children (dict) and value_sum (sum of values for words ending below).

Step 2: Insert Key-Value:

Traverse or create path for key.
Update value_sum at each node by adding new value (and subtracting old if overwriting).
Store key-value in hash map for overwrite tracking.

Step 3: Sum Prefix:

Traverse to prefix end in trie.
Return value_sum at that node (or 0 if prefix not found).

Step 4: Return Result:

Return computed sum.

It’s like a trie tally—build and sum!

Step-by-Step Example

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

Step 1: Init:

Trie root: children={}, value_sum=0.
Map: {}.

Step 2: Insert "apple", 3:

Path: a→p→p→l→e.
Each node: value_sum += 3.
Map: {"apple": 3}.
Trie: a(3)→p(3)→p(3)→l(3)→e(3).

Step 3: Insert "app", 2:

Path: a→p→p.
Each node: value_sum += 2.
Map: {"apple": 3, "app": 2}.
Trie: a(5)→p(5)→p(5)→l(3)→e(3).

Step 4: Sum "ap":

Traverse: a(5)→p(5), return 5.

Output: 5.

Example: insert("apple", 5) (overwrite)

Step 2: Insert "apple", 5:

Old val = 3, diff = 5 - 3 = 2.
Path: a→p→p→l→e, add 2 to each value_sum.
Map: {"apple": 5, "app": 2}.
Trie: a(7)→p(7)→p(7)→l(5)→e(5).

Step 4: Sum "ap":

Traverse: a(7)→p(7), return 7.

Output: 7.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class TrieNode:
    def __init__(self):
        self.children = {}  # Dict of char to TrieNode
        self.value_sum = 0  # Sum of values for words passing through

class MagicDictionary:
    def __init__(self):
        self.root = TrieNode()
        self.value_map = {}  # Key-value storage for overwrites

    def insert(self, key: str, val: int) -> None:
        # Step 1: Handle overwrite
        diff = val
        if key in self.value_map:
            diff = val - self.value_map[key]
        self.value_map[key] = val

        # Step 2: Update trie with difference
        node = self.root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.value_sum += diff

    def sum(self, prefix: str) -> int:
        # Step 3: Traverse to prefix and return sum
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.value_sum

Lines 1-5: TrieNode: Children dict, value_sum for prefix sums.
Lines 8-11: __init__: Root node, hash map for values.
Lines 13-25: insert:

Calculate diff for overwrite, update map, increment value_sum along path.

Lines 27-35: sum:

Traverse to prefix end, return value_sum or 0 if not found.

Time Complexity: Insert O(l), Sum O(l)—l = key length.
Space Complexity: O(n * l)—trie size.

This is like a prefix ledger—track and tally!

Alternative Solution: Hash Map with Prefix Iteration

Why an Alternative Approach?

The hash map with prefix iteration approach uses a simple dictionary—O(n * l) insert and sum time, O(n * l) space. It’s easier to grasp, iterating over all keys to check prefixes, but less efficient for frequent sum calls. It’s like keeping a flat list and manually summing every matching entry!

How It Works

Picture this as a prefix scanner:

Step 1: Store key-value pairs in hash map.
Step 2: Insert:

Update or add key-value pair.

Step 3: Sum:

Iterate over map, sum values where key starts with prefix.

Step 4: Return result.

It’s like a map counter—store and scan!

Step-by-Step Example

Example: Same as above

Step 1: Map = {}.
Step 2: Insert "apple", 3:

Map = {"apple": 3}.

Step 2: Insert "app", 2:

Map = {"apple": 3, "app": 2}.

Step 3: Sum "ap":

Check "apple": Starts with "ap", add 3.
Check "app": Starts with "ap", add 2.
Total = 5.

Output: 5.

Code for Hash Map Approach

class MagicDictionary:
    def __init__(self):
        self.map = {}

    def insert(self, key: str, val: int) -> None:
        self.map[key] = val

    def sum(self, prefix: str) -> int:
        total = 0
        for key, val in self.map.items():
            if key.startswith(prefix):
                total += val
        return total

Lines 4-5: __init__: Empty hash map.
Lines 7-8: insert: Add or update key-value pair.
Lines 10-15: sum:

Iterate, sum values for prefix matches.

Time Complexity: Insert O(1), Sum O(n * l)—n keys, l length check.
Space Complexity: O(n * l)—map storage.

It’s a prefix adder—list and sum!

Comparing the Two Solutions

Trie (Best):

Pros: O(l) insert and sum, O(n * l) space, fast for searches.
Cons: Trie structure less obvious.

Hash Map (Alternative):

Pros: O(n l) sum, O(n l) space, simple.
Cons: Slower for frequent sums.

Trie wins for efficiency.

Additional Examples and Edge Cases

Input: insert("a", 1), sum("b")

Output: 0.

Input: insert("abc", 2), insert("abcd", 3), sum("abc")

Output: 5.

Trie handles these well.

Complexity Breakdown

Trie: Insert O(l), Sum O(l), Space O(n * l).
Hash Map: Insert O(1), Sum O(n l), Space O(n l).

Trie is optimal for sum.

Key Takeaways

Trie: Prefix summing—smart!
Hash Map: Prefix scanning—clear!
Pairs: Tallying is fun.
Python Tip: Tries rock—see Python Basics.

Final Thoughts: Tally Those Pairs

LeetCode 677: Map Sum Pairs in Python is a fun dictionary challenge. Trie with prefix sum offers speed and elegance, while hash map provides a clear baseline. Want more? Try LeetCode 208: Implement Trie or LeetCode 676: Implement Magic Dictionary. Ready to count? Head to Solve LeetCode 677 on LeetCode and sum those prefixes today!