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 key key with the value value at the given time timestamp.
• String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_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 and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 107
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 105 calls will be made to set and get.

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)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏