DSAPrep
MediumBinary Search

Time Based Key Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.

void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.

String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example 1

Input: ["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output: [null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation: set("foo","bar",1) stores value bar at timestamp 1. get("foo",1) returns bar. get("foo",3) returns bar since the closest timestamp <= 3 is still 1. set("foo","bar2",4) stores a newer value. get("foo",4) and get("foo",5) both return bar2.

Constraints

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 10^7
  • All the timestamps of set are strictly increasing, for a given key.
  • At most 2 * 10^5 calls will be made to set and get.
View original on LeetCode ↗

This is a design problem rather than a single-answer algorithm, so there is no input array to trace — the interesting part is the data layout that makes get fast. The optimal solution below steps through that layout directly: the per-key store rows, and the binary search get runs over them.

Store and Linear Scan

Time set: O(1), get: O(n)Space O(n)

For each key, keep a list of (timestamp, value) pairs in the order they were set. Since the problem guarantees timestamps for a given key are strictly increasing, that list comes for free already sorted by timestamp. A correct get can simply scan the list from the most recent entry backwards and return the first value whose timestamp is <= timestamp. This is correct, but for a key with many versions, every get call can cost O(n).

class TimeMap:
    def __init__(self):
        self.store: dict[str, list[tuple[int, str]]] = {}


    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:
        result = ""
        for ts, val in reversed(self.store.get(key, [])):
            if ts <= timestamp:
                result = val
                break
        return result

Binary Search Over Stored Timestamps

OptimalTime set: O(1), get: O(log n)Space O(n)

The scan in get is wasteful precisely because the list is already sorted by timestamp — that is a binary search opportunity. Keep the timestamps and values for each key in parallel, already-sorted lists (appending is O(1) since new timestamps are always larger than existing ones), then binary search for the rightmost timestamp that does not exceed the query. That is the same “find the last index satisfying a condition” binary search used in find-minimum-in-rotated-sorted-array, just applied to a per-key timestamp list instead of the whole input array.

class TimeMap:
    def __init__(self):
        self.timestamps: dict[str, list[int]] = {}
        self.values: dict[str, list[str]] = {}


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


    def get(self, key: str, timestamp: int) -> str:
        ts_list = self.timestamps.get(key, [])
        val_list = self.values.get(key, [])
        lo, hi = 0, len(ts_list) - 1
        result = ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if ts_list[mid] <= timestamp:
                result = val_list[mid]   # candidate answer, but a later index might be closer
                lo = mid + 1
            else:
                hi = mid - 1
        return result

The mechanism is the layout plus the search acting together, so the trace below replays the statement example on the real store (trace data lives in this folder’s data.ts). Watch lo/mid/hi narrow the row, the mid chip being compared, and the candidate upgrade each time a newer entry satisfies the <= query condition — the returned value is always the rightmost chip whose timestamp does not exceed the query:

init

store["foo"] · pairs already sorted by timestamp

nothing stored yet — the row appears on the first set
empty — the row is created lazily on the first set
1 / 12
search rangemid being examinedreturned valueseen, ruled out

The store starts empty. Each key will own two parallel lists — `timestamps` and `values` — where one index in both lists describes one set call. Timestamps for a key are strictly increasing, so each list is born sorted, and that sorted order is what turns `get` from a scan into a binary search.

All four get results above — bar, bar, bar2, bar2 — match the expected output [null, null, "bar", "bar", null, "bar2", "bar2"].

Why it’s correct: because timestamps for a key are strictly increasing, the stored list is sorted, so “the value with the largest timestamp_prev <= timestamp” is exactly the rightmost element satisfying ts_list[mid] <= timestamp. The loop keeps every index that satisfies the condition as a candidate (result = val_list[mid]) while continuing to search further right for a better one, and discards indices that fail the condition along with everything after them. Complexity: set only appends, O(1). get binary searches a list of at most n timestamps, giving O(log n) time; storage is O(n) across all keys.