Leetcode 981: Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/description/



Notes:

This question is pretty straightforward, and it is essentially a question of data structure + binary search. See the code below,

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {

    }

    void set(string key, string value, int timestamp) {
        if(ump.count(key) == 0) ump[key].push_back({timestamp, value});
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        ump[key].insert(it, {timestamp, value});
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = upper_bound(ump[key].begin(), ump[key].end(), pair<int, string>(timestamp, ""));
        if(it != ump[key].end() && it->first == timestamp) return it->second;
        if(it == ump[key].begin()) return "";
        return (it-1)->second;
    }
private:
    unordered_map<string, vector<pair<int, string>>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

It should be noticed that inside the upper_bound(), the type of pair has to be written explicitly as pair<int, string>, otherwise compiler error will occur.

Another way using a different structure. Pay attention to the property of map.upper_bound().

int _=[](){//increase run spead
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 return 0;
 }();

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
       
    }
   
    void set(string key, string value, int timestamp) {
        ump[key][timestamp] = value;
    }

    string get(string key, int timestamp) {
        if(ump.count(key) == 0) return "";
        auto it = ump[key].upper_bound(timestamp); //find the upper bound of the key of the map...
        if(it == ump[key].begin()) return "";
        return (--it)->second;
    }

private:
    unordered_map<string, map<int, string>> ump;
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */