LC 981 · Medium · Template B · upper bound + design
Time Based Key-Value Store
Values stamped with increasing times, and a query asking for the most recent one at or before some moment.
Recognise it
Before any code, what in the question tells you this is the pattern?
A design question ("build a class with set/get") where get takes a timestamp and wants the value from the most recent set at or before it. Because timestamps arrive strictly increasing, each key's history is already sorted. Binary search hiding inside an OOP wrapper.
The brute force
Always have this one ready. It is the honest starting point, and it is what the real solution improves on.
Store every write in a list per key, and on a get, walk that list backwards until you meet a timestamp at or before the query.
O(1) for a set and O(n) for a get, where n is the number of writes for that key.
It is fine when reads are rare, and worth saying so. It degrades when one key is written many times and read often, which is the case these problems are built to punish. The fix is available for free: writes arrive with increasing timestamps, so the list per key is already sorted and never needs sorting.
The approach
The idea in plain language, before it becomes syntax.
Keep a map from key to a list of time and value pairs, appended in arrival order. Because the problem guarantees timestamps increase, each list is sorted with no extra work, and a set stays constant time.
A get is then a search for a boundary rather than an exact match, and that difference matters. You are not asking where the query time appears. You are asking for the last entry whose time is at or before the query, which may not be present at all.
The clean way to express that is an upper bound: find the first index whose timestamp is strictly greater than the query, then step back one. If that index is 0 then every stored entry is later than the query and the answer is the empty string. This framing also handles duplicate timestamps correctly, since stepping back from the first strictly-greater entry lands on the last matching one.
The algorithm
The same idea again, as steps you could follow with a pencil.
The solution
Now the code, and why each decision in it is the way it is.
class TimeMap:
def __init__(self):
self.store = {} # key -> [(ts, value), ...]
def set(self, key, value, timestamp):
self.store.setdefault(key, []).append((timestamp, value))
def get(self, key, timestamp):
arr = self.store.get(key, [])
lo, hi, res = 0, len(arr) - 1, ""
while lo <= hi: # rightmost ts <= target
mid = (lo + hi) // 2
if arr[mid][0] <= timestamp:
res = arr[mid][1] # candidate, look righter
lo = mid + 1
else:
hi = mid - 1
return reshi starts at n rather than n - 1. An upper bound search runs over insertion positions, not element positions, and the answer can legitimately be "past the end".
The comparison is stamp[mid] <= query, which pushes lo past every entry that is early enough. When the loop ends, lo is the count of entries at or before the query, so lo - 1 is the index of the one you want.
Check for lo == 0 before indexing. Skipping that check reads index -1, which throws in most languages and silently returns the last element in Python.
Where people slip
- Don't re-sort on insert. Timestamps are guaranteed increasing, so append is O(1) and keeps order.
- The search is "rightmost timestamp ≤ target": record the candidate when
ts <= target, then keep pushing lo right. - Return "" (empty) when nothing qualifies. Handle the no-match branch explicitly.
Your notes
What tripped you up here? Write it in your own words.