Leetcode 1023 Solution

This article provides solution to leetcode question 1023 (time-based-key-value-store)

https://leetcode.com/problems/time-based-key-value-store

Solution

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.m = collections.defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        values = self.m.get(key, [])

        l = 0
        r = len(values) - 1

        while l < r:
            m = (l + r + 1) // 2
            if values[m][0] > timestamp:
                r = m - 1
            else:
                l = m

        if values[l][0] <= timestamp:
            return values[l][1]
        else:
            return ""


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)