677. Map Sum Pairs LeetCode Solution

In this guide, you will get 677. Map Sum Pairs LeetCode Solution with the best time and space complexity. The solution to Map Sum Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Map Sum Pairs solution in C++
Map Sum Pairs solution in Java
Map Sum Pairs solution in Python
Additional Resources

677. Map Sum Pairs LeetCode Solution image

Problem Statement of Map Sum Pairs

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.

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 <= 50
key and prefix consist of only lowercase English letters.
1 <= val <= 1000
At most 50 calls will be made to insert and sum.

Complexity Analysis

Time Complexity: O(|\texttt{prefix}|)
Space Complexity: O(|\texttt{insert()})

677. Map Sum Pairs LeetCode Solution in C++

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  int sum = 0;
  TrieNode() : children(26) {}
};

class MapSum {
 public:
  void insert(string key, int val) {
    const int diff = val - keyToVal[key];
    shared_ptr<TrieNode> node = root;
    for (const char c : key) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
      node->sum += diff;
    }
    keyToVal[key] = val;
  }

  int sum(string prefix) {
    shared_ptr<TrieNode> node = root;
    for (const char c : prefix) {
      const int i = c - 'a';
      if (node->children[i] == nullptr)
        return 0;
      node = node->children[i];
    }
    return node->sum;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
  unordered_map<string, int> keyToVal;
};
/* code provided by PROGIEZ */

677. Map Sum Pairs LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public int sum = 0;
}

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

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

  private TrieNode root = new TrieNode();
  private Map<String, Integer> keyToVal = new HashMap<>();
}
// code provided by PROGIEZ

677. Map Sum Pairs LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}
    self.sum = 0


class MapSum:
  def __init__(self):
    self.root = TrieNode()
    self.keyToVal = {}

  def insert(self, key: str, val: int) -> None:
    diff = val - self.keyToVal.get(key, 0)
    node: TrieNode = self.root
    for c in key:
      node = node.children.setdefault(c, TrieNode())
      node.sum += diff
    self.keyToVal[key] = val

  def sum(self, prefix: str) -> int:
    node: TrieNode = self.root
    for c in prefix:
      if c not in node.children:
        return 0
      node = node.children[c]
    return node.sum
 # code by PROGIEZ