algoadvance

Leetcode 677. Map Sum Pairs

Problem Statement

You are tasked with implementing the MapSum class, which supports the following two methods:

1. void insert(String key, int val): Inserts the key-value pair into the map. If the key already exists, the original key-value pair will be overridden to the new one.
2. int sum(String prefix): Returns the sum of all the pairs’ values whose keys start with the specified prefix.

Clarifying Questions

1. Q: Can the keys contain non-alphabetic characters? A: For this problem, we can assume keys are strings consisting of lowercase English letters.

2. Q: Could there be any constraints on the length of keys or the number of key-value pairs? A: The problem does not specify constraints. We can assume typical constraints for such problems where the input size is manageable within memory limits of typical competitive programming environments.

3. Q: How should we handle an insert operation with a key that already exists? A: If the key already exists, the existing value must be replaced with the new value provided during the insert operation.

Strategy

1. Data Structures:
   • We will use a HashMap to store the key-value pairs.
   • We need to efficiently sum values with a specific prefix, which suggests using a Trie (prefix tree) data structure. Each node in the Trie will carry:
     • A Map to its children nodes.
     • A variable to keep track of the sum of values of keys that pass through or terminate at that node.
2. Insert Operation:
   • Insert the key-value pair into the HashMap.
   • Traverse through the Trie from root to the end of the key, updating the sum at each node.
3. Sum Operation:
   • Traverse the Trie nodes according to the prefix.
   • Once at the end of the prefix node, return the sum stored in that node.

Code

import java.util.HashMap;
import java.util.Map;

class MapSum {
    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        int value = 0;
    }

    private TrieNode root;
    private Map<String, Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        for (char c : key.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
            node.value += delta;
        }
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) {
                return 0;
            }
        }
        return node.value;
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple", 3);
        System.out.println(mapSum.sum("ap")); // Output: 3
        mapSum.insert("app", 2);
        System.out.println(mapSum.sum("ap")); // Output: 5
    }
}

Time Complexity

• Insert Operation: O(L) where L is the length of the key. This is because we traverse the key to update the Trie and HashMap.
• Sum Operation: O(P) where P is the length of the prefix. We only traverse the Trie nodes up to the length of the prefix.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?