Q51: Time Based Key-Value Store. - DSA Patterns (Multi-Lang)

In Simple Words: Hash Map of lists of (timestamp, value). Timestamps are appended in monotonically increasing order. get() runs binary search for greatest timestamp $\le target$.

Time: set: $O(1)$, get: $O(\log N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)  # key -> list of [val, timestamp]

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

    def get(self, key: str, timestamp: int) -> str:
        values = self.store.get(key, [])
        l, r = 0, len(values) - 1
        res = ""
        while l <= r:
            mid = l + (r - l) // 2
            if values[mid][1] <= timestamp:
                res = values[mid][0]
                l = mid + 1
            else:
                r = mid - 1
        return res