Leetcode 0981. Time Based Key-Value Store

Problem statement

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

Solution

Keep for every key pari (value, timestamp). For get funtcion use binary search, notice that we need to use key (timestamp, element > z). Be careful, “Z” is smaller than z!, so use { for example.

Complexity

It is O(1) for append and O(log n) for get.

Code

class TimeMap:
    def __init__(self):
        self.t_v = defaultdict(list)

    def set(self, key, value, timestamp):
        self.t_v[key].append((timestamp, value))

    def get(self, key, timestamp):
        i = bisect.bisect(self.t_v[key], (timestamp, "{") )
        return self.t_v[key][i - 1][1] if i else ""