Time Based Key-Value Store

How it works

Each key stores its values in the order they were inserted, and timestamps are guaranteed to be increasing for each key.
This means we can keep a simple list of (value, timestamp) pairs for every key.

To answer a get(key, timestamp) query, we only need to find the latest timestamp that is ≤ the given timestamp.
Because timestamps are sorted, we can use binary search to quickly find this position instead of scanning everything.

This gives an efficient and clean approach:
store values in arrays, then binary-search timestamps when retrieving.

Steps

1. Use a dictionary:
   • key → list of [value, timestamp]
   • Timestamps for each key are stored in sorted order (because they arrive in increasing order).
2. set(key, value, timestamp):
   • Append [value, timestamp] to the key’s list.
3. get(key, timestamp):
   • If the key does not exist, return "".
   • Let arr be the list of [value, timestamp] pairs.
   • Perform binary search on timestamps to find the rightmost timestamp t ≤ timestamp.
   • If found, return the corresponding value.
   • If not found, return "".

Complexity

• Time complexity: O(1) for set() and O(log n) for get().
• Space complexity: O(m * n)

Where n is the total number of values associated with a key and m is the total number of keys.

Things to watch for

Using Exact Match Instead of Floor Search

A common mistake is searching for an exact timestamp match instead of finding the largest timestamp less than or equal to the query. Binary search should find the rightmost value satisfying timestamp <= query, not an exact match. If no exact match exists but earlier timestamps do, returning an empty string is incorrect.

Off-By-One Errors in Binary Search

Binary search boundaries are tricky. Using bisect_left instead of bisect_right, or not adjusting the index after the search, leads to returning values from timestamps greater than the query. Always verify your binary search returns the correct floor value by testing edge cases like querying before any set operation.

Returning Empty String When Key Exists But Timestamp Is Too Early

When a key exists but all stored timestamps are greater than the query timestamp, the correct behavior is to return an empty string. Some implementations incorrectly return the earliest stored value instead. Always check that your found index is valid (non-negative) before accessing the value.

class TimeMap:

    def __init__(self):
        self.keyStore = {}  # key : list of [val, timestamp]

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = []
        self.keyStore[key].append([value, timestamp])

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

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> keyStore;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        keyStore[key].emplace_back(timestamp, value);
    }

    string get(string key, int timestamp) {
        auto& values = keyStore[key];
        int left = 0, right = values.size() - 1;
        string result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values[mid].first <= timestamp) {
                result = values[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
};