We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Map Sum Pairs

Difficulty: Medium

Problem Description

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.

Key Insights

  • A trie (prefix tree) can be used to efficiently store keys and their corresponding values, allowing for quick retrieval of sums based on prefixes.
  • Keeping track of the total value for each node in the trie facilitates the calculation of sums for any given prefix.
  • When inserting a key, if it already exists, we should update its value and adjust the sums in the trie accordingly.

Space and Time Complexity

Time Complexity:

  • insert: O(m) where m is the length of the key.
  • sum: O(n) where n is the number of characters in the prefix.

Space Complexity:

  • O(m * k) where m is the number of unique keys and k is the average length of the keys stored in the trie.

Solution

To solve the problem, we will use a trie data structure. Each node in the trie will represent a character in the keys, and we will store cumulative sums at each node to facilitate quick sum retrieval for any prefix.

  1. Create a MapSum class that contains a trie for storing keys and their values.
  2. Implement the insert method to add or update a key-value pair, adjusting the sums in the trie accordingly.
  3. Implement the sum method to return the total value of all keys that start with the given prefix by traversing the trie.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.sum = 0
        self.value = 0

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

    def insert(self, key: str, val: int) -> None:
        node = self.root
        if key in self.map:
            old_value = self.map[key]
            # Decrement the sum of the prefix for the old value
            self._decrement_sum(node, key, old_value)
        self.map[key] = val
        # Increment the sum of the prefix for the new value
        self._increment_sum(node, key, val)

    def sum(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.sum

    def _increment_sum(self, node: TrieNode, key: str, val: int) -> None:
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.sum += val

    def _decrement_sum(self, node: TrieNode, key: str, val: int) -> None:
        for char in key:
            node = node.children[char]
            node.sum -= val
← Back to All Questions