Abstract / Summary

Implement a map that supports inserting key value pairs and calculating the sum of values for keys starting with a given prefix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 57% (200k+ submissions).

Typical patterns to solve this problem:

• Design
• Hash Table
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a MapSum class that stores string keys associated with integer values and can compute the sum of all values whose keys share a given prefix. The class maintains an internal dictionary for direct key-value mapping and leverages sorting combined with binary search to locate the relevant subset of keys efficiently during a sum query.

Core Components

Initialization

The constructor creates an empty dictionary that will hold the mapping from keys to their integer values.

class MapSum:
    def __init__(self):
        self.data = {}

The use of a plain dictionary ensures constant-time insertion and direct value lookup for any exact key.

Insert Operation

The insert method receives a key and a value, then stores the pair in the internal dictionary, overwriting any existing entry with the same key.

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

Because the dictionary handles key collisions internally, the method does not need additional logic to manage duplicate keys.

Sum Operation

The sum method calculates the total of values whose keys begin with the supplied prefix. The procedure follows several distinct steps:

1. Result Initialization - A variable result is set to zero to accumulate the running total.

2. Key Sorting - All current keys are extracted from the dictionary and sorted lexicographically, producing a list k.

        k = sorted(self.data.keys())

Sorting creates an ordered sequence that enables binary search, allowing the algorithm to skip irrelevant keys without scanning the entire dictionary.

3. Binary Search for Starting Position - The bisect_left function locates the leftmost index where the prefix could appear in the sorted list. This index, stored in pos, marks the first candidate key that might match the prefix.

        pos = bisect_left(k, prefix)

4. Iterative Prefix Matching - Starting from pos, the method walks forward through the sorted list while each key still begins with the prefix. For each matching key, the corresponding value from the dictionary is added to result. The loop terminates as soon as a key no longer satisfies the prefix condition, guaranteeing that only relevant entries are processed.

        while pos < len(k) and k[pos].startswith(prefix):
            result += self.data[k[pos]]
            pos += 1

5. Return the Accumulated Sum - After the loop finishes, the method returns the computed total.

        return result

Edge Cases Handled

When the internal dictionary is empty, the sorted key list is also empty, causing the binary search to return position zero. The subsequent while-loop condition fails immediately, and the method returns the initial zero result, correctly representing the sum of an empty set.

If the supplied prefix does not match any existing key, bisect_left yields the insertion point where such a key would belong. Because the next key in the sorted list either does not exist or does not start with the prefix, the while-loop body is never executed, and the method again returns zero.

When a key exactly equals the prefix, the startswith check succeeds, and its value contributes to the sum. The algorithm continues to include any longer keys that share the same prefix, ensuring comprehensive coverage of all matching entries.

Performance Optimizations

The design exploits the ordered nature of a sorted key list to limit the work performed during a sum query. By using binary search (bisect_left) to jump directly to the first possible match, the algorithm avoids a linear scan of unrelated keys. The subsequent linear walk proceeds only over the contiguous block of keys that share the prefix, terminating as soon as a non-matching key appears. This approach reduces the number of startswith checks compared to scanning the entire dictionary.

Storing values in a dictionary provides O(1) access when retrieving a value for a matching key, eliminating the need for additional lookups or data structures during the accumulation phase.

Overall, the combination of dictionary storage, sorted key ordering, binary search, and early loop termination yields a solution that scales well with the number of stored keys while keeping each operation concise and focused.

Think of this code like a magical filing cabinet for words and their secret numbers. When starting out, the cabinet is completely empty and ready to store whatever items are handed to it.

The insert part is how information gets tucked away inside. Every word acts like a label on a folder, and the number is the secret score tucked inside that folder. If the same label is used again, the old score is just swapped out for the new one.

The sum part is like playing a scavenger hunt. It looks for all the folders that start with a specific set of letters. It first puts all the folder labels in alphabetical order, just like a dictionary. Then, it finds the right spot to start looking. It walks through the folders one by one, checking if the label begins with those special letters. Every time a match is found, it adds the score from that folder to a running total. It keeps going down the row until it reaches a word that does not start with those letters, stopping right before it wanders too far.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	JS	Rust		Go	C#	TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem						Ruby
	fengvyi	C++
	halfrost							Go
	JoshCrozier				JS
	lkwq007		Python
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality