Time Based Key-Value Store

PracticeNeetCode ↗LeetCode ↗

Design a time-based key-value store that can hold multiple values for the same key at different timestamps, and retrieve the value for a key as of a given timestamp — specifically, the value recorded at the largest timestamp not exceeding the query timestamp, or an empty string if none exists.

Example

Key Pointers

• Set calls for a given key always arrive in increasing timestamp order, so each key's list of entries is already sorted by the time it's queried — no sorting needed at query time.
• "Largest timestamp not exceeding the query" is a classic binary search for an upper bound, not an exact-match search.
• A dict of key to a list of (timestamp, value) pairs, binary searched per get, is all the structure this needs.

Step-by-Step Analysis

1. set: append the new (timestamp, value) pair to the list stored under that key.
2. get: if the key has never been set, return an empty string.
3. Binary search the key's entry list for the rightmost timestamp that does not exceed the query timestamp.
4. Track the best match found while narrowing the search, since an exact timestamp hit is rare.
5. Return that match's value, or an empty string if no entry qualifies.

Complexity

Time: O(1) for set, O(log n) for get — Space: O(n)

Code

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

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""

        entries = self.store[key]
        left, right = 0, len(entries) - 1
        result = ""

        while left <= right:
            mid = left + (right - left) // 2
            if entries[mid][0] <= timestamp:
                result = entries[mid][1]
                left = mid + 1
            else:
                right = mid - 1

        return result

Code Explanation

How the solution above works, piece by piece.

1. store maps each key to a list of (timestamp, value) pairs.
2. set appends. Timestamps arrive in increasing order, so the list stays sorted with no extra work: O(1).
3. get binary-searches that list for the last timestamp ≤ the requested one.
4. Whenever entries[mid][0] <= timestamp, it's a valid answer: remember it and look right for a later one. Otherwise look left.
5. If no entry is early enough, result stays "". get is O(log n) per call.

Visual Walkthrough

Running the example calls on key "foo":

Video Explanation

NeetCode — LeetCode 981