981. Time Based Key-Value Store — LeetCode(Python)
I got you!
Problem:
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.
Implement the TimeMap
class:
TimeMap()
Initializes the object of the data structure.void set(String key, String value, int timestamp)
Stores the keykey
with the valuevalue
at the given timetimestamp
.String get(String key, int timestamp)
Returns a value such thatset
was called previously, withtimestamp_prev <= timestamp
. If there are multiple such values, it returns the value associated with the largesttimestamp_prev
. If there are no values, it returns""
.
Example 1:
Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1); // return "bar"
timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4); // return "bar2"
timeMap.get("foo", 5); // return "bar2"
Constraints:
1 <= key.length, value.length <= 100
key
andvalue
consist of lowercase English letters and digits.1 <= timestamp <= 107
- All the timestamps
timestamp
ofset
are strictly increasing. - At most
2 * 105
calls will be made toset
andget
.
Solution:
class TimeMap: def __init__(self):
self.timeMap = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.timeMap:
self.timeMap[key] = []
self.timeMap[key].append([value, timestamp]) def get(self, key: str, timestamp: int) -> str:
res = '' #default return value
values = self.timeMap.get(key, [])
l, r = 0, len(values) - 1
while l <= r:
m = (l + r) // 2
if values[m][1] <= timestamp:
res = values[m][0]
l = m + 1
else:
r = m - 1
return res
Explanation —
We use the ever powerful hash map to solve this problem.
In the init function, we initialize an empty dictionary, timeMap.
In the set function, we store the key-value pairs by mapping key to value and timestamp.
In the get function,
- we initialize our result res to an empty string, which is the default answer.
- next, we store all value lists in values.
- then, we perform binary search on our list of lists values.
- since we are asked to return the closest greatest value to timestamp in case the unique timestamp doesn’t exist, we keep storing every valid timestamp in res and keep updating it.
- finally, res is returned.
Time and Space Complexity —
Our binary search operation requires logarithmic time and constant space.
In the worst case, all values and timestamps can be mapped to one key and thus every timestamp needs to be searched.
Our overall space complexity depends on whether the hash map is counted towards extra space.
Thus, if n is the number of distinct values in the dictionary timeMap,
Time Complexity: O(logn)
Space Complexity: O(1)