Problem statement

https://binarysearch.com/problems/Historical-Map/

Solution

Equal to Leetcode 0981. Time Based Key-Value Store, but here we need to keep sorted list for each key, because times not neccesary increasing. Also we need to deal with cases, when we have (value, time) equal to (2, 3) and then (1, 3), then we need to overwrite element.

Complexity

It is O(log n) for get and set for time and O(n) for space.

Code

class HistoricalMap:
    def __init__(self):
        self.t_v = defaultdict(SortedList)

    def set(self, key, value, timestamp):
        idx = self.t_v[key].bisect((timestamp, float("inf")))
        if idx and self.t_v[key][idx-1][0] == timestamp: self.t_v[key].pop(idx-1)
        self.t_v[key].add((timestamp, value))

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