[981. Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/)

--- tags: leetcode --- # [981. Time Based Key-Value Store](https://leetcode.com/problems/time-based-key-value-store/) --- # My Solution ## The Key Idea for Solving This Coding Question ## C++ Code ```cpp= struct valueData { string value; int timestamp; valueData(string value, int timestamp) : value(value), timestamp(timestamp) {} }; class TimeMap { public: TimeMap() { } void set(string key, string value, int timestamp) { htbl[key].push_back(valueData(value, timestamp)); } string get(string key, int timestamp) { auto iter = htbl.find(key); if (iter == htbl.end()) { return ""; } vector<valueData> &valueList = iter->second; if (timestamp < valueList[0].timestamp) { return ""; } if (valueList.back().timestamp < timestamp) { return valueList.back().value; } int left = 0, right = valueList.size() - 1; while (left < right) { int middle = left + (right - left + 1) / 2; if (timestamp < valueList[middle].timestamp) { right = middle - 1; } else { left = middle; } } if (timestamp < valueList[left].timestamp) { --left; } return valueList[left].value; } private: unordered_map<string, vector<valueData>> htbl; }; /** * 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); */ ``` ## Time Complexity * `TimeMap` $O(1)$ * `set` $O(1)$ * `get` $O(logn)$ $n$ is the number of values associated with the queried `key`. ## Space Complexity * `TimeMap` $O(1)$ * `set` $O(m \cdot n)$ $m$ is the number of `key`. $n$ is the number of values of their own `key`. * `get` $O(1)$ # Miscellane