677. Map Sum Pairs

1. Description

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.

2. Example

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)

3. 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.

4. Solutions

My Accepted Solution

n = stringValue.size(), p = i_prefix.size()
Time complexity
MapSum: O(1)
insert: O(1)
sum: O(np)
Space complexity
MapSum: O(1)
insert: O(p)
sum: O(p)

// brute force
class MapSum {
private:
    unordered_map<string, int> stringValue;

public:
    MapSum() {}

    void insert(const string& i_key, int val) {
        stringValue[i_key] = val;
    }

    int sum(const string& i_prefix) {
        int prefixSum = 0;
        for (auto iter : stringValue) {
            if (iter.first.compare(0, i_prefix.size(), i_prefix) == 0) {
                prefixSum += iter.second;
            }
        }

        return prefixSum;
    }
};

n = stringValue.size(), l = i_key.size()
Time complexity
MapSum: O(1)
insert: O($l^2$)
sum: O(1)
Space complexity
MapSum: O(1)
insert: O(l)
sum: O(1)

// prefix hash
class MapSum {
public:
    MapSum() {}

    void insert(const string& i_key, int val) {
        // delete the old prefix value
        int oldPrefixValue = stringValue[i_key];
        stringValue[i_key] = val;

        for (int i = 1; i < i_key.size(); ++i) {
            auto prefix = i_key.substr(0, i);

            prefixValue[prefix] -= oldPrefixValue;
            prefixValue[prefix] += val;
        }
    }

    int sum(const string& i_prefix) {
        return prefixValue[i_prefix];
    }

private:
    unordered_map<string, int> stringValue;
    unordered_map<string, int> prefixValue;
};

n = stringValue.size(), p = i_prefix.size(), l = i_key.size()
Time complexity
MapSum: O(1)
insert: O(l)
sum: O(p)
Space complexity
MapSum: O(1)
insert: O(l)
sum: O(1)

// trie
class TrieNode {
public:
    unordered_map<char, TrieNode*> childs;
    int value;

    TrieNode() : value(0) {}
};

class MapSum {
public:
    MapSum() {
        prefixValue = new TrieNode();
    }

    void insert(const string& i_key, int val) {
        // delete the old prefix value
        int oldPrefixValue = stringValue[i_key];
        stringValue[i_key] = val;

        auto iter = prefixValue;
        for (auto letter : i_key) {
            if(iter->childs[letter] == nullptr) {
                iter->childs[letter] = new TrieNode();
            }
            
            iter = iter->childs[letter];

            iter->value -= oldPrefixValue;
            iter->value += val;
        }
    }

    int sum(const string& i_prefix) {
        auto iter = prefixValue;
        for (auto letter : i_prefix) {
            iter = iter->childs[letter];
            
            if(iter == nullptr) {
                return 0;
            }
        }

        return iter->value;
    }

private:
    unordered_map<string, int> stringValue;
    TrieNode* prefixValue;
};

Algorithm Solutions

Search

Tags

1. Description

2. Example

3. Constraints

4. Solutions

My Accepted Solution