Back to DSA

Map Sum Pairs

medium
Acceptance: 47%
TrieHash TableDesign

Design a key-value map where keys are strings and values are integers. It must support two operations: insert(key, val) associates the key with the given value (overwriting any previous value), and sum(prefix) returns the total of all values whose keys start with the given prefix.

Examples

Example 1:
Input:MapSum(), insert('tree', 5), sum('tr'), insert('treat', 3), sum('tr')
Output:[null,null,5,null,8]

Hints

Related Problems

Min StackmediumNext Greater Element IeasyOnline Stock SpanmediumImplement Queue using StackseasyTop K Frequent Elementsmedium
00:00
import java.util.*;

class MapSum {
    private Map<String, Integer> map = new HashMap<>();
    private TrieNode root = new TrieNode();

    public void insert(String key, int val) {
        int diff = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
            node.sum += diff;
        }
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return 0;
            node = node.children[idx];
        }
        return node.sum;
    }

    class TrieNode { TrieNode[] children = new TrieNode[26]; int sum = 0; }
}
Time complexityO(m) for both operations
Space complexityO(n * m)