Skip to content
16-Week DSA Roadmap
LeetCode #981MediumProblem 3 of 8

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

The problem in plain English

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) saves value under key at time timestamp. Old values are not overwritten; every version is kept.
  • get(key, timestamp) returns the value of key as it was at time timestamp: 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.

timestamps for 'foo'
  1. 10
  2. 41
values
  1. bar
  2. bar2
After set('foo', 'bar', 1) and set('foo', 'bar2', 4), the key 'foo' has two versions. get('foo', 3) returns 'bar': time 1 is the latest time that isn't after 3.

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.

How LeetCode runs a design problem

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"

Before you code: think it through

So the plan has two parts:

  1. 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 (Map in JavaScript, dict in Python). Since timestamps only grow, appending to the end keeps every list sorted by time for free.
  2. Lookup: in a sorted list, find the last timestamp that is ≤ t. That’s a binary search.
store1 item
keylist of (timestamp, value)
a[1:v1, 3:v3, 5:v5, 8:v8, 12:v12]
The store after five sets on key 'a': one sorted list per key.

Pause and think

Key 'a' has timestamps [1, 3, 5, 8, 12]. What should get('a', 9) return? And get('a', 0)?

Approach 1: Scan backwards

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)

store0 items
keylist of (timestamp, value)
empty
variables
call
new TimeMap()
t
—
answer
—
output (what LeetCode checks)
  1. null
  • Checking now
  • Too new (checked)
  • Returned

Create the object with an empty store.

Step 1 / 8

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 time

Why is it slow?

set 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 pattern: binary search over sorted timestamps

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

Template

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”
  1. Constructor: create an empty hash map store.
  2. set: if the key is new, give it an empty list. Append (timestamp, value) to its list.
  3. get: if the key was never set, return "".
  4. Binary search the key’s list with lo = 0, hi = len − 1, and answer = "".
  5. If items[mid]’s timestamp is ≤ t, save its value in answer and move right: lo = mid + 1.
  6. Otherwise it’s too new: move left with hi = mid − 1.
  7. When lo > hi, return answer.

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)

store0 items
keylist of (timestamp, value)
empty
variables
call
new TimeMap()
t
—
answer
—
output (what LeetCode checks)
  1. 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.

Step 1 / 23

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;  }}

The code, line by line

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 answer

On 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.store belongs 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; answer starts 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 after t? 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.

Dry run

The “Longer list” example: key a has timestamps [1, 3, 5, 8, 12], and we call get("a", 9):

lohimiditems[mid] time≤ 9?answernext
0425yes"v5"lo = 3
3438yes"v8"lo = 4
44412no"v8"hi = 3
43——lo > hi"v8"return "v8"
items = [(1,v1), (3,v3), (5,v5), (8,v8), (12,v12)], get("a", 9)

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.

Complexity

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.

Common mistakes and edge cases

What to say out loud:

  1. “Each key needs all its versions, so I’ll map key → list of (timestamp, value).”
  2. “Timestamps arrive in increasing order, so appending keeps each list sorted.”
  3. “get needs the latest timestamp ≤ t: that’s a binary search for the last ‘yes’ in a sorted list.”
  4. “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 set becomes 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.