algoadvance

Leetcode 677. Map Sum Pairs

Problem Statement

Leetcode Problem 677: Map Sum Pairs

Implement the MapSum class that supports two operations:

  1. void insert(string key, int val): Inserts the key-value pair into the map. If the key already existed, 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 given prefix.

Clarifying Questions

  1. Q: What should be the behavior if the same key is inserted multiple times with different values?
    • A: The later value should override the existing value.
  2. Q: Is it allowed for keys to contain non-alphabetical characters?
    • A: Yes, keys can contain any valid string characters.
  3. Q: What are the constraints on the length of keys and values?
    • A: There are no explicit constraints on key lengths or values, but they should fit within reasonable usage parameters in a typical application.
  4. Q: How frequent are the sum queries compared to insert operations?
    • A: This might affect the choice of data structure. Typically, a prefix tree (Trie) could be beneficial for fast prefix-based queries.

Strategy

To efficiently support both operations, we will use a combination of a HashMap and a Trie (prefix tree):

  1. HashMap (for storing key-value pairs):
    • This will ensure O(1) time complexity for insertions and updates.
  2. Trie (for prefix sum computation):
    • Each node in the Trie will keep track of the sum of all values of keys that share the prefix represented by the node.
    • Insertion will update both the HashMap and the Trie.
    • When inserting, if a key already exists, we’ll update the Trie nodes to reflect the change in value.

Time Complexity:

Code Implementation

#include <unordered_map>
#include <string>

using namespace std;

class TrieNode {
public:
    int valueSum;
    unordered_map<char, TrieNode*> children;
    TrieNode() : valueSum(0) {}
};

class MapSum {
private:
    TrieNode* root;
    unordered_map<string, int> keyValueMap;
    
public:
    /** Initialize your data structure here. */
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        int delta = val;
        if (keyValueMap.find(key) != keyValueMap.end()) {
            delta -= keyValueMap[key];
        }
        keyValueMap[key] = val;
        
        TrieNode* node = root;
        for (char c : key) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
            node->valueSum += delta;
        }
    }
    
    int sum(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return 0;
            }
            node = node->children[c];
        }
        return node->valueSum;
    }
};

Explanation:

  1. Insert Operation:
    • Compute the delta value: the difference between the new value and the old value if the key existed.
    • Traverse the Trie node by node, updating the valueSum by the delta at each node corresponding to characters of the key.
  2. Sum Operation:
    • Traverse the Trie node by node corresponding to characters of the prefix.
    • If the Trie lacks nodes for some characters in the prefix, return 0 (indicates no keys with such prefix).
    • Otherwise, return the valueSum at the final node which represents the sum of all values of keys sharing the given prefix.

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