LeetCode 981 - Time Based Key-Value Store

2026-07-07

medium　hash map　binary search　design

If you're not familiar with binary search, check out LeetCode 704 - Binary Search first.

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the value at a specific timestamp.

Implement the TimeMap class:

• TimeMap() — initializes the data structure.
• void set(String key, String value, int timestamp) — stores key with value at timestamp.
• String get(String key, int timestamp) — returns the value for key at the largest timestamp_prev <= timestamp among all stored entries. If no such entry exists, return "".

Example 1:

Input:
["TimeMap", "set", ["alice", "happy", 1], "get", ["alice", 1],
 "get", ["alice", 2], "set", ["alice", "sad", 3], "get", ["alice", 3]]

Output:
[null, null, "happy", "happy", null, "sad"]

Explanation:

TimeMap timeMap = new TimeMap();
timeMap.set("alice", "happy", 1);  // store ("alice", "happy") at t=1
timeMap.get("alice", 1);           // return "happy"
timeMap.get("alice", 2);           // return "happy" — no entry at t=2, use t=1
timeMap.set("alice", "sad", 3);    // store ("alice", "sad") at t=3
timeMap.get("alice", 3);           // return "sad"

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 0 <= timestamp <= 10^7
• All timestamps passed to set are strictly increasing.

Solution:

class TimeMap:
    # Approach: HashMap of sorted (timestamp, value) lists + Binary Search
    # Since set() is always called with strictly increasing timestamps,
    # each key's list is naturally sorted by timestamp — no explicit sorting needed.
    #
    # set(): append (timestamp, value) to the list for the given key. O(1).
    #
    # get(): binary search the key's list for the largest timestamp <= the query timestamp.
    #   - If an exact match is found, return its value immediately.
    #   - If the query timestamp is larger than mid's timestamp, move left pointer right
    #     (there might be a closer match to the right).
    #   - If smaller, move right pointer left.
    #   - When the loop exits, r_idx points to the largest timestamp that did not exceed
    #     the query. If r_idx >= 0, that entry is the answer; otherwise return "".
    # Time Complexity: set O(1), get O(log N) where N = number of entries for the key.
    # Space Complexity: O(total number of set calls).

    def __init__(self):
        self.time_map = {}

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

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

        key_list = self.time_map[key]
        l_idx, r_idx = 0, len(key_list) - 1
        while l_idx <= r_idx:
            mid = (l_idx + r_idx) // 2
            if timestamp == key_list[mid][0]:
                return key_list[mid][1]
            elif timestamp > key_list[mid][0]:
                l_idx = mid + 1
            else:
                r_idx = mid - 1

        if r_idx >= 0:
            return key_list[r_idx][1]
        return ""

Conclusion

Today we designed a time-based key-value store that supports floor-timestamp reads.

The storage structure is straightforward: a dictionary mapping each key to a list of (timestamp, value) tuples. Because the problem guarantees that set is always called with strictly increasing timestamps, these lists are already sorted — no extra work needed.

The interesting part is get. We need the largest stored timestamp that does not exceed the query timestamp — a classic "floor" query. Binary search handles this exactly. When the loop exits without an exact match, r_idx has settled at the last position where the stored timestamp was still smaller than the query. If r_idx >= 0, that entry is the answer; if the query timestamp is smaller than everything stored (r_idx fell below 0), we return "".

The strictly-increasing constraint on set is the key enabler here — it means we get a sorted list for free, and binary search can run without any preprocessing. Without that guarantee, we would need to sort on every set or use a sorted container.