Time Based Key-Value Store
Build a key-value store that remembers every version of a value, and answers "what was the value at time t?" with binary search.
- Binary search over sorted timestamps
- Hash map of lists
- Design a class
Before this, know: Classic binary search (week 3), Hash maps (Map in JavaScript, dict in Python), Classes and methods
This is a design problem: instead of writing one function, you write a class (a blueprint for an object that keeps its own data between calls) with three parts:
TimeMap()creates an empty store.set(key, value, timestamp)savesvalueunderkeyat timetimestamp. Old values are not overwritten; every version is kept.get(key, timestamp)returns the value ofkeyas it was at timetimestamp: the one saved with the latest timestamp that is ≤timestamp. If there is none, return""(an empty string).
Think of a shared document’s version history: “show me the document as it was at 3 o’clock” means the last save at or before 3.
- 10
- 41
- bar
- bar2
The rule that makes this problem easier than it looks: the timestamps passed to
set are strictly increasing. Every new set happens later than all the
previous ones.
LeetCode gives you two lists: the method names to call, and the
arguments for each call. It creates your object, calls the methods in order,
and collects every return value into an output list (null for the constructor
and for set, which return nothing):
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"]
That’s the same as running this by hand:
const tm = new TimeMap(); // nulltm.set("foo", "bar", 1); // nulltm.get("foo", 1); // "bar"tm.get("foo", 3); // "bar" (nothing newer than time 1 yet)tm.set("foo", "bar2", 4); // nulltm.get("foo", 4); // "bar2"tm.get("foo", 5); // "bar2"tm = TimeMap() # nulltm.set("foo", "bar", 1) # nulltm.get("foo", 1) # "bar"tm.get("foo", 3) # "bar" (nothing newer than time 1 yet)tm.set("foo", "bar2", 4) # nulltm.get("foo", 4) # "bar2"tm.get("foo", 5) # "bar2"So the plan has two parts:
- Storage: a hash map from each key to its own list of
(timestamp, value)pairs. A hash map stores key → value pairs and finds a key in about one step (Mapin JavaScript,dictin Python). Since timestamps only grow, appending to the end keeps every list sorted by time for free. - Lookup: in a sorted list, find the last timestamp that is ≤
t. That’s a binary search.
| key | list of (timestamp, value) |
|---|---|
| a | [1:v1, 3:v3, 5:v5, 8:v8, 12:v12] |
Pause and think
get('a', 9): the timestamps ≤ 9 are 1, 3, 5, 8. The latest is 8, so return
"v8".
get('a', 0): no timestamp is ≤ 0 (the first save was at time 1), so the key
didn’t exist yet. Return "".
Store the lists the same way. For get, start at the newest entry and walk
backwards; the first timestamp that is ≤ t is the answer.
Brute force: scan backwards from the newest
set("a","v1",1), set("a","v3",3), set("a","v5",5), set("a","v8",8), set("a","v12",12), get("a",9)
| key | list of (timestamp, value) | |
|---|---|---|
| empty | ||
- call
- new TimeMap()
- t
- —
- answer
- —
- null
- Checking now
- Too new (checked)
- Returned
Create the object with an empty store.
Which line is running?
class TimeMap { constructor() {Running now: this.store = new Map(); // key -> list of [timestamp, value], oldest first } set(key, value, timestamp) { if (!this.store.has(key)) this.store.set(key, []); this.store.get(key).push([timestamp, value]); } get(key, timestamp) { const items = this.store.get(key) ?? []; for (let i = items.length - 1; i >= 0; i--) { if (items[i][0] <= timestamp) return items[i][1]; // newest one that is old enough } return ""; // nothing was set at or before this time }}Brute force: backward scan in get
class TimeMap { constructor() { this.store = new Map(); // key -> list of [timestamp, value], oldest first } set(key, value, timestamp) { if (!this.store.has(key)) this.store.set(key, []); this.store.get(key).push([timestamp, value]); } get(key, timestamp) { const items = this.store.get(key) ?? []; for (let i = items.length - 1; i >= 0; i--) { if (items[i][0] <= timestamp) return items[i][1]; // newest one that is old enough } return ""; // nothing was set at or before this time }}class TimeMap: def __init__(self): self.store = {} # key -> list of (timestamp, value), oldest first def set(self, key, value, timestamp): if key not in self.store: self.store[key] = [] self.store[key].append((timestamp, value)) def get(self, key, timestamp): items = self.store.get(key, []) for i in range(len(items) - 1, -1, -1): if items[i][0] <= timestamp: return items[i][1] # newest one that is old enough return "" # nothing was set at or before this timeset is fast: one append. But get may walk the whole list. If a key has been
set 200,000 times (the problem allows up to 2 × 10⁵ calls) and we keep asking for
an early time, each get checks up to 200,000 entries. 100,000 such gets would be
about 20 billion checks. Each get is
O(n) in the length of that key’s list.
The list is sorted by time, so we can binary search it (see the basics in week 3). But we aren’t looking for an exact match: we want the last position whose timestamp is ≤ t. That variant is called a floor or “last ≤ t” search. It’s one position before the “upper bound” (the first timestamp greater than t), which is why the Python shortcut below subtracts 1.
Pattern
Binary search over sorted timestamps
Use it when: data arrives in time order and you need the latest entry at or before a given time (or the last value ≤ x).
Signal words
- “timestamp”
- “latest at or before”
- “largest value ≤ x”
- “version history”
- “strictly increasing”
- Constructor: create an empty hash map
store. - set: if the key is new, give it an empty list. Append
(timestamp, value)to its list. - get: if the key was never set, return
"". - Binary search the key’s list with
lo = 0,hi = len − 1, andanswer = "". - If
items[mid]’s timestamp is≤ t, save its value inanswerand move right:lo = mid + 1. - Otherwise it’s too new: move left with
hi = mid − 1. - When
lo > hi, returnanswer.
Each example below is a whole LeetCode call sequence. Watch the store fill up,
the binary search inside each get, and the output list grow at the bottom. The
“Longer list” example shows the search properly; the last one shows a time
that’s too early and a key that was never set.
TimeMap with binary search in get
set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5)
| key | list of (timestamp, value) | |
|---|---|---|
| empty | ||
- call
- new TimeMap()
- t
- —
- answer
- —
- null
- Just appended / just output
- items[mid]
- Best candidate so far (≤ t)
- Ruled out
- Returned
LeetCode first creates the object. Our store starts empty: a hash map from each key to its own list of (timestamp, value) pairs.
Which line is running?
class TimeMap { constructor() {Running now: this.store = new Map(); // key -> list of [timestamp, value], oldest first } set(key, value, timestamp) { if (!this.store.has(key)) this.store.set(key, []); this.store.get(key).push([timestamp, value]); // timestamps only grow, so the list stays sorted } get(key, timestamp) { const items = this.store.get(key); if (items === undefined) return ""; // key never set let lo = 0; let hi = items.length - 1; let answer = ""; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (items[mid][0] <= timestamp) { answer = items[mid][1]; // old enough: remember it, then look for a later one lo = mid + 1; } else { hi = mid - 1; // too new: look further left } } return answer; }}TimeMap with binary search
class TimeMap { constructor() { this.store = new Map(); // key -> list of [timestamp, value], oldest first } set(key, value, timestamp) { if (!this.store.has(key)) this.store.set(key, []); this.store.get(key).push([timestamp, value]); // timestamps only grow, so the list stays sorted } get(key, timestamp) { const items = this.store.get(key); if (items === undefined) return ""; // key never set let lo = 0; let hi = items.length - 1; let answer = ""; while (lo <= hi) { const mid = Math.floor((lo + hi) / 2); if (items[mid][0] <= timestamp) { answer = items[mid][1]; // old enough: remember it, then look for a later one lo = mid + 1; } else { hi = mid - 1; // too new: look further left } } return answer; }}class TimeMap: def __init__(self): self.store = {} # key -> list of (timestamp, value), oldest first def set(self, key, value, timestamp): if key not in self.store: self.store[key] = [] self.store[key].append((timestamp, value)) # timestamps only grow, so the list stays sorted def get(self, key, timestamp): if key not in self.store: return "" # key never set items = self.store[key] lo, hi = 0, len(items) - 1 answer = "" while lo <= hi: mid = (lo + hi) // 2 if items[mid][0] <= timestamp: answer = items[mid][1] # old enough: remember it, then look for a later one lo = mid + 1 else: hi = mid - 1 # too new: look further left return answerOn LeetCode, JavaScript’s starter code may use the older var TimeMap = function() {}
style with TimeMap.prototype.set = ...; a class like ours does the same job.
Python’s starter code is a class already, with self as the first parameter of
every method (self is the object itself, like this in JavaScript).
- JS 2–3 / Py 2–3: the constructor runs once, when LeetCode creates the
object.
this.store/self.storebelongs to the object, so it survives between calls. - JS 7 / Py 6–7: first time we see a key, give it an empty list.
- JS 8 / Py 8: append the pair. Because each new timestamp is bigger than the last, the list stays sorted without us doing anything.
- JS 12–13 / Py 11–13: no list means the key was never set: return
"". - JS 14–16 / Py 14–15: the search range is the whole list;
answerstarts as"", which is exactly what we must return if every timestamp is too new. - JS 18 / Py 17: the middle index, rounded down.
- JS 19–21 / Py 18–20:
items[mid][0]is the timestamp,items[mid][1]the value. Not aftert? It’s a valid answer, but a later one might also be valid, so remember it and search to the right. - JS 23 / Py 22: too new; everything to its right is newer still, so search left.
- JS 26 / Py 23: the last remembered value is the latest one at or before
t.
The “Longer list” example: key a has timestamps [1, 3, 5, 8, 12], and we call
get("a", 9):
| lo | hi | mid | items[mid] time | ≤ 9? | answer | next |
|---|---|---|---|---|---|---|
| 0 | 4 | 2 | 5 | yes | "v5" | lo = 3 |
| 3 | 4 | 3 | 8 | yes | "v8" | lo = 4 |
| 4 | 4 | 4 | 12 | no | "v8" | hi = 3 |
| 4 | 3 | — | — | lo > hi | "v8" | return "v8" |
The first row (time 5) finds a valid answer ("v5") but doesn’t stop: there
might be a later one. The time-8 row finds it ("v8"), and the time-12 row
confirms that 12 is too new.
Backward scan
Time
set O(1), get O(n)
n is the number of versions stored for that key. A get for an early time walks almost all of them.
Space
O(total sets)
Every (timestamp, value) pair is kept.
Binary search in get
Time
set O(1), get O(log n)
Appending is one step. Each get halves its search range: 200,000 versions need about 18 checks.
Space
O(total sets)
Same storage: one list entry per set call.
What to say out loud:
- “Each key needs all its versions, so I’ll map key → list of (timestamp, value).”
- “Timestamps arrive in increasing order, so appending keeps each list sorted.”
- “get needs the latest timestamp ≤ t: that’s a binary search for the last ‘yes’ in a sorted list.”
- “set is O(1), get is O(log n).”
Likely follow-ups:
- “What if timestamps could arrive out of order?” Then appending no longer keeps
the list sorted. You’d insert in sorted position, or use a sorted structure
(like a balanced tree), and
setbecomes slower. - “Many gets, few sets?” The binary search is already the right call.
Related problems:
- Koko Eating Bananas: binary search where you remember the best “yes”.
- Binary Search (LeetCode 704) in week 3: the exact-match version this builds on.
- Search Insert Position (LeetCode 35): another “find the boundary” search, a good extra exercise.