Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
Design a map that allows you to do the following:
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 <= 50key and prefix consist of only lowercase English letters.1 <= val <= 100050 calls will be made to insert and sum.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design · Trie
["MapSum","insert","sum","insert","sum"] [[],["apple",3],["ap"],["app",2],["ap"]]
sort-the-jumbled-numbers)sum-of-prefix-scores-of-strings)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #677: Map Sum Pairs
class Trie {
private Trie[] children = new Trie[26];
private int val;
public void insert(String w, int x) {
Trie node = this;
for (int i = 0; i < w.length(); ++i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
node.val += x;
}
}
public int search(String w) {
Trie node = this;
for (int i = 0; i < w.length(); ++i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
return 0;
}
node = node.children[idx];
}
return node.val;
}
}
class MapSum {
private Map<String, Integer> d = new HashMap<>();
private Trie trie = new Trie();
public MapSum() {
}
public void insert(String key, int val) {
int x = val - d.getOrDefault(key, 0);
d.put(key, val);
trie.insert(key, x);
}
public int sum(String prefix) {
return trie.search(prefix);
}
}
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
// Accepted solution for LeetCode #677: Map Sum Pairs
type trie struct {
children [26]*trie
val int
}
func (t *trie) insert(w string, x int) {
for _, c := range w {
c -= 'a'
if t.children[c] == nil {
t.children[c] = &trie{}
}
t = t.children[c]
t.val += x
}
}
func (t *trie) search(w string) int {
for _, c := range w {
c -= 'a'
if t.children[c] == nil {
return 0
}
t = t.children[c]
}
return t.val
}
type MapSum struct {
d map[string]int
t *trie
}
func Constructor() MapSum {
return MapSum{make(map[string]int), &trie{}}
}
func (this *MapSum) Insert(key string, val int) {
x := val - this.d[key]
this.d[key] = val
this.t.insert(key, x)
}
func (this *MapSum) Sum(prefix string) int {
return this.t.search(prefix)
}
/**
* Your MapSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(key,val);
* param_2 := obj.Sum(prefix);
*/
# Accepted solution for LeetCode #677: Map Sum Pairs
class Trie:
def __init__(self):
self.children: List[Trie | None] = [None] * 26
self.val: int = 0
def insert(self, w: str, x: int):
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.val += x
def search(self, w: str) -> int:
node = self
for c in w:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return 0
node = node.children[idx]
return node.val
class MapSum:
def __init__(self):
self.d = defaultdict(int)
self.tree = Trie()
def insert(self, key: str, val: int) -> None:
x = val - self.d[key]
self.d[key] = val
self.tree.insert(key, x)
def sum(self, prefix: str) -> int:
return self.tree.search(prefix)
# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
// Accepted solution for LeetCode #677: Map Sum Pairs
struct Trie {
children: Vec<Option<Box<Trie>>>,
val: i32,
}
impl Trie {
fn new() -> Self {
Trie {
children: (0..26).map(|_| None).collect(),
val: 0,
}
}
fn insert(&mut self, w: &str, x: i32) {
let mut node = self;
for c in w.chars() {
let idx = (c as usize) - ('a' as usize);
if node.children[idx].is_none() {
node.children[idx] = Some(Box::new(Trie::new()));
}
node = node.children[idx].as_mut().unwrap();
node.val += x;
}
}
fn search(&self, w: &str) -> i32 {
let mut node = self;
for c in w.chars() {
let idx = (c as usize) - ('a' as usize);
if node.children[idx].is_none() {
return 0;
}
node = node.children[idx].as_ref().unwrap();
}
node.val
}
}
struct MapSum {
d: std::collections::HashMap<String, i32>,
trie: Trie,
}
impl MapSum {
fn new() -> Self {
MapSum {
d: std::collections::HashMap::new(),
trie: Trie::new(),
}
}
fn insert(&mut self, key: String, val: i32) {
let x = val - self.d.get(&key).unwrap_or(&0);
self.d.insert(key.clone(), val);
self.trie.insert(&key, x);
}
fn sum(&self, prefix: String) -> i32 {
self.trie.search(&prefix)
}
}
// Accepted solution for LeetCode #677: Map Sum Pairs
class Trie {
children: Trie[];
val: number;
constructor() {
this.children = new Array(26);
this.val = 0;
}
insert(w: string, x: number) {
let node: Trie = this;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (!node.children[i]) {
node.children[i] = new Trie();
}
node = node.children[i];
node.val += x;
}
}
search(w: string): number {
let node: Trie = this;
for (const c of w) {
const i = c.charCodeAt(0) - 97;
if (!node.children[i]) {
return 0;
}
node = node.children[i];
}
return node.val;
}
}
class MapSum {
d: Map<string, number>;
t: Trie;
constructor() {
this.d = new Map();
this.t = new Trie();
}
insert(key: string, val: number): void {
const x = val - (this.d.get(key) ?? 0);
this.d.set(key, val);
this.t.insert(key, x);
}
sum(prefix: string): number {
return this.t.search(prefix);
}
}
/**
* Your MapSum object will be instantiated and called as such:
* var obj = new MapSum()
* obj.insert(key,val)
* var param_2 = obj.sum(prefix)
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.