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"]ExplanationTimeMap 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:

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

## More from Palash Sharma

A student of science | palashsharma891@gmail.com | https://github.com/palashsharma891 | https://www.linkedin.com/in/palashsharma891/