Course4all
Join us on telegram
Home/dsa/Trie/Map Sum Pairs

Map Sum Pairs

Master this topic with zero to advance depth.

Map Sum Pairs

Calculate sum of all values whose key starts with a specific prefix.

Medium
Approach 1

Level III: Trie with Pre-calculated Sums (Optimal)

Intuition

Each trie node stores the sum of values for all words passing through it. When updating a key, we first find its old value to calculate the delta and update all nodes in the path.

⏱ Insert: O(L), Sum: O(L).💾 O(N * L * 26).

Detailed Dry Run

Insert('apple', 3): Nodes a,p,p,l,e each get +3 sum. Insert('app', 2): Nodes a,p,p get +2. Sum('ap') -> 5.

java
import java.util.*;
class MapSum {
    class Node { Node[] children = new Node[26]; int sum = 0; }
    Node root = new Node();
    Map<String, Integer> map = new HashMap<>();
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        Node curr = root;
        for(char c : key.toCharArray()) {
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new Node();
            curr = curr.children[i];
            curr.sum += delta;
        }
    }
    public int sum(String prefix) {
        Node curr = root;
        for(char c : prefix.toCharArray()) {
            curr = curr.children[c - 'a'];
            if(curr == null) return 0;
        }
        return curr.sum;
    }
}
← Previous QuestionAdd and Search Word
Next Question →Replace Words