The problem
Design a key-value store that keeps history. set(key, value, time) stores a value at a time; get(key, time) returns the value set at the latest time that is ≤ the asked time, or "" if there is none. Times for set are increasing.
Input: set mood happy 1, set mood calm 4, set mood sleepy 7, set mood hungry 9,
get mood 5, get mood 9, get mood 0
Output: "calm", "hungry", ""Picture it
Picture a diary for each key. Every set writes a new page stamped with the time. To answer “what was the mood at time 5?”, flip to the last page written at or before 5. Since pages are already in time order, we don’t flip through all of them: we binary search for the right page.
How to recognise it
- You must design a class that stores a history of values per key and answers "what was it at time t?".
- The question is "the latest entry at or before t": a last position where a condition holds, which is a boundary search.
setis called with increasing times, so appending to a list keeps each key's history sorted for free. No sorting step is needed.- Up to 2 × 10^5 calls, so scanning a key's whole history on every
getis too slow.
Start with brute force
Store (time, value) pairs per key, as the shown code does, and let get scan the whole list, keeping the last value whose time is not after t.
from collections import defaultdict
class TimeMapBrute:
def __init__(self):
self.pages = defaultdict(list)
def set(self, key, value, time):
self.pages[key].append((time, value))
def get(self, key, time):
ans = ""
for t, v in self.pages[key]:
if t <= time:
ans = v
return ans
set is O(1), but get is O(k) for a key with k entries. With 10^5 sets on one key followed by 10^5 gets, that is about 10^10 steps.
From brute force to the idea
- Find the waste. The history is sorted by time, but the scan ignores that and reads every entry.
- Name the target. You want the last page whose time is at most
time. Times at or before it form a prefix of the list, so there is one boundary to find. - Binary search, remembering the best so far. Keep
lo..hiinclusive. Ifpages[mid][0] <= time, this page is a valid answer, so record its value inans, then look further right for a later one:lo = mid + 1. Otherwise the page is too late:hi = mid - 1. - The last recorded value wins. Each time
ansis updated, it is at a later valid position than before, so when the range emptiesansholds the latest one. - Nothing found means "".
ansstarts as"", which is exactly what the problem wants when every page is aftertime, or the key was never set.
This is the key idea: keep each key's pages in time order and binary search for the last page whose time is at most t.
The key idea
Store (time, value) lists per key in time order; get = binary search for the last time ≤ t. O(log n) per get.
Python solution
class TimeMap:
def __init__(self):
self.pages = defaultdict(list) # key -> [(time, value)]
def set(self, key, value, time):
self.pages[key].append((time, value)) # times only increase
def get(self, key, time):
pages, ans = self.pages[key], ""
lo, hi = 0, len(pages) - 1
while lo <= hi: # last page with time <= t
mid = (lo + hi) // 2
if pages[mid][0] <= time:
ans, lo = pages[mid][1], mid + 1
else:
hi = mid - 1
return ansLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | set O(1); get O(k): scans all k entries of the key | O(total sets) |
| Binary search (shown code) | set O(1) amortised; get O(log k) | O(total sets) |
Edge cases
- Imports: the shown code needs
from collections import defaultdict; without it, creating aTimeMapraisesNameError. - The example:
get("mood", 5)is"calm",get("mood", 9)is"hungry",get("mood", 0)is"". - Exact time match (
get("mood", 4)): returns"calm", because the comparison is<=. - Time after the last set (
get("mood", 100)): returns"hungry". - Unknown key: returns
"", butself.pages[key]on adefaultdictcreates an empty list for that key. Many gets for unknown keys therefore use memory.self.pages.get(key, [])avoids it. - The increasing-times promise: if
setwere called out of order, the list would not be sorted and the search could return wrong values. The shown code does not check.
Common mistakes
- Using
<instead of<=, which skips the entry set at exactly the asked time. - Returning
pages[hi][1]after the loop without checkinghi >= 0. When every time is too late,hiis −1 and Python quietly returns the last page. - Storing one dictionary per key of
time -> valueand looking up the exact time. That fails for any time between two sets. - Sorting the list inside
get, which costs O(k log k) per call.
Add get_range(key, t1, t2) that returns, in time order, every value set for the key at a time between t1 and t2 inclusive. For the example, get_range("mood", 4, 8) is ["calm", "sleepy"]. Describe your approach, then write it if you like.
Compare with our answer
Find both ends of the window with two binary searches: the first time at or after t1, and the first time after t2. The values between those positions are the answer. Keeping times and values in two parallel lists lets Python's bisect module do the searches.
from bisect import bisect_left, bisect_right
from collections import defaultdict
class TimeLog:
def __init__(self):
self.times = defaultdict(list)
self.values = defaultdict(list)
def set(self, key, value, time):
self.times[key].append(time)
self.values[key].append(value)
def get_range(self, key, t1, t2):
ts = self.times[key]
i = bisect_left(ts, t1) # first time >= t1
j = bisect_right(ts, t2) # first time > t2
return self.values[key][i:j]
Time O(log k + r) for r returned values. If t1 > t2 the slice is empty.
A strong answer mentions: which side each search is biased to (left for t1, right for t2), why the slice end is exclusive, and the O(log k + r) cost.
1. A stock service records each symbol's price whenever it changes, in time order, and must answer "what was the price at 14:03:27?". Which approach fits best?
Prices arrive in time order, so the list is already sorted and a binary search finds the last change at or before t in O(log k). An exact-time dictionary fails between changes, popping a heap destroys the history, and a backward scan is O(k).
2. Why does get record ans before moving lo = mid + 1, instead of returning at once?
The goal is the latest valid page, not any valid page, so the search keeps going right. Saving ans ensures that the best valid page seen so far survives if nothing later qualifies.
3. A learner changes the test to if pages[mid][0] < time:. Using the example, which call now returns the wrong value?
At time 4 there is a page with exactly that time, and the strict test rejects it, so the function returns "happy". The other times fall between pages or outside them, where < and <= agree.
Score 60% or more and the lesson is marked complete.