Time Based Key-Value Store (LeetCode 981)

The problem

Design a class TimeMap with two methods:

• set(key, value, timestamp) stores value for key at time timestamp.
• get(key, timestamp) returns the value that was set for key at the largest timestamp <= timestamp. If there is none, it returns "".

Timestamps passed to set are strictly increasing across all calls.

set("foo", "bar", 1)
set("foo", "bar2", 4)
get("foo", 1) -> "bar"
get("foo", 3) -> "bar"
get("foo", 4) -> "bar2"
get("foo", 5) -> "bar2"

At time 3, the most recent value for foo was set at time 1, so it’s "bar".

How to think about it

Start with brute force. Store a list of (timestamp, value) per key, and on get scan backwards for the first timestamp <= t. set is O(1) but get is O(n) per call for a key with n entries. With up to 200,000 calls this can be too slow.

Notice what you get for free. Timestamps arrive in increasing order. So if you just append to each key’s list, the list is already sorted by timestamp. No sorting, no tree, no extra work on set.

The key insight: “largest timestamp <= t” is a boundary search. In a sorted list, the entries with timestamp <= t form a prefix. bisect_right finds the first position past that prefix, so the answer is the entry just before it, at index bisect_right(...) - 1. If that index is -1, every entry is newer than t and you return "".

Searching a list of tuples. bisect compares whole tuples, so the code searches for (t, chr(127)). Tuples compare by timestamp first, and only on a tie by value. chr(127) sorts after any lowercase-letter value, so (t, chr(127)) lands after every entry with timestamp exactly t, which is what bisect_right needs.

Which pattern is this? A hash map plus binary search on a sorted list: “predecessor” or “floor” lookup. The tell is versioned or timestamped data and the phrase “the most recent value at or before”.

Approach

1. Keep store, a dictionary from key to a list of (timestamp, value) pairs.
2. set(key, val, t): append (t, val) to store[key]. The list stays sorted.
3. get(key, t): let arr = store[key]. Find i = bisect_right(arr, (t, chr(127))) - 1.
4. Return arr[i][1] if i >= 0, otherwise "".

Solution

import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)          # key -> [(timestamp, value)], sorted by time
    def set(self, key, val, t):
        self.store[key].append((t, val))        # timestamps arrive increasing: stays sorted
    def get(self, key, t):
        arr = self.store[key]
        i = bisect.bisect_right(arr, (t, chr(127))) - 1   # last entry with timestamp <= t
        return arr[i][1] if i >= 0 else ""
# set("foo","bar",1); set("foo","bar2",4)
# get("foo",1)->"bar", get("foo",3)->"bar", get("foo",4)->"bar2", get("foo",5)->"bar2"

Dry run

After the two set calls, store["foo"] = [(1, "bar"), (4, "bar2")]:

At t = 4, the probe (4, chr(127)) sorts after (4, "bar2"), so the search lands at 2 and the entry before it is the time-4 value.

Complexity

• Time: set is O(1) (a list append). get is O(log n), where n is the number of entries for that key.
• Space: O(N) for all N stored entries.

Edge cases and pitfalls

• Unknown key: defaultdict returns an empty list, bisect_right returns 0, i = -1, and you return "". Note that the lookup also inserts an empty list for that key; use self.store.get(key, []) if that matters.
• t earlier than every timestamp for the key also returns "".
• The chr(127) sentinel relies on values being plain ASCII letters, as the problem promises. A safer, value-free version keeps a separate list of timestamps per key and runs bisect_right(times, t), or uses bisect_right(arr, t, key=lambda e: e[0]) on Python 3.10+.
• Using bisect_left on the timestamp would miss an exact match at t, unless you adjust the index.

Related problems

• Find First and Last Position of Element in Sorted Array (LeetCode 34): the same bisect_right - 1 trick for the last occurrence.
• LRU Cache (LeetCode 146): another key-value design problem with strict per-operation costs.
• Search Insert Position (LeetCode 35): the lower-bound search that bisect implements.