Leetcode 981. Time Based Key-Value Store

Problem

Leetcode 981 - Time Based Key-Value Store

Example:

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"

Approach

We can use implement this with dicitonary where each key stores array where every element consists of (value, timestamp)

Using this data structure, we can use binary search to get the value by comparing the timestamp value.

Visualization of the Approach:

TimeMap timeMap = new TimeMap() 
timeMap = {}

timeMap.set("foo", "bar", 1); 
timeMap = {"foo" : [("bar", 1)]}

timeMap.get("foo", 1);
arr = [("bar", 1)]
left = 0, right = 0
Since arr[mid][1] <= timestamp, update res
res = arr[mid][0] = "bar"
return "bar"

timeMap.get("foo", 3);
arr = [("bar", 1)]
left = 0, right = 0
Since arr[mid][1] <= timestamp, update res
res = arr[mid][0] = "bar"
return "bar"

timeMap.set("foo", "bar2", 4);
timeMap = {"foo" : [("bar", 1), ("bar2", 4)]}

timeMap.get("foo", 4);   
arr = [("bar", 1), ("bar2", 4)]
left = 0, right = 1
Since arr[mid][1] <= timestamp, update res and left so we can find value that's closest to timestamp
res = arr[mid][0] = "bar"

left = 1, right = 1
Since arr[mid][1] <= timestamp, update res and left so we can find value that's closest to timestamp
res = arr[mid][1] = "bar2"
return "bar2"

timeMap.get("foo", 5); 
arr = [("bar", 1), ("bar2", 4)]
left = 0, right = 1
Since arr[mid][1] <= timestamp, update res and left so we can find value that's closest to timestamp
res = arr[mid][0] = "bar"

left = 1, right = 1
Since arr[mid][1] <= timestamp, update res and left so we can find value that's closest to timestamp
res = arr[mid][1] = "bar2"
return "bar2"

Here is the Python code for the solution:

class TimeMap:
    def __init__(self):
        self.map = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.map:
            self.map[key] = []
        self.map[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        arr = self.map.get(key, [])
        res = ''
        left, right = 0, len(arr)-1

        while left <= right:
            mid = (left+right) // 2

            if arr[mid][1] <= timestamp:
                res = arr[mid][0]
                left = mid+1
            else:
                right = mid-1
        return res

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for set() and $O(log n)$ for get()

Space Complexity: $O(m * n)$ where $m$ is total number of keys and $n$ is total number of values associated with key