981. Time Based Key-Value Store

Design a key-value store that remembers every version of a value together with its timestamp. set appends in order; get uses binary search to locate the most recent value at or before the queried timestamp in O(log n) time.

● MediumBinary SearchHash MapDesignTypeScript

PROBLEM What we're solving

Implement a TimeMap class with two operations. set(key, value, timestamp) stores a value under a key at a given time. get(key, timestamp) returns the value most recently set at or before that timestamp, or "" if none exists. The problem guarantees timestamps passed to set are strictly increasing for each key.

Worked example. After:

set("love", "10", 1)
set("love", "20", 2)

Then get("love", 1) → "10", get("love", 3) → "20" (closest past version), get("love", 0) → "" (no version yet at ts=0).

KEY IDEA Per-key sorted list + binary search

Insight → because setis called with strictly increasing timestamps, each key's list is automatically sorted by time — no sorting step needed. That means get can binary-search for the largest timestamp ≤ query (the rightmost valid entry) in O(log n), instead of scanning the whole history.

RECIPE Append on set, binary-search on get

0 · Initialize. A Map<string, {ts, val}[]> holds one append-only list per key.
1 · set(key, value, timestamp). Create the list if absent, then push { ts: timestamp, val: value }. Because timestamps are strictly increasing the list stays sorted — O(1) amortized.
2 · get(key, timestamp). Fetch the list. If empty, return "".
3 · Binary search for floor. Standard lower-bound search: while lo <= hi, compute mid. If list[mid].ts <= timestamp, record ans = mid and advance lo right (try to find something even closer). Otherwise pull hi left.
4 · Return. ans === -1 ? "" : list[ans].val. The -1 sentinel means every stored timestamp was larger than the query.

Classic confusion → the binary search condition is list[mid].ts <= timestamp (not strict <). Using strict less-than would skip exact timestamp matches and return the wrong earlier value. An exact match is always a valid answer and should be recorded as a candidate before searching further right.

COST Complexity & alternatives

Linear scan on get

O(n)

Walk the list backward until ts ≤ query. Simple but slow.

Binary search (this approach)

O(log n)

set O(1) append; get O(log n) binary search; O(n) total space.

Space: O(total set calls) — each call appends one entry. No deduplication needed because each timestamp is unique per key.

Pattern transfer → the "floor in sorted list" binary search appears in Search in Rotated Sorted Array (modified bounds), Find First and Last Position (lower-bound + upper-bound), and Koko Eating Bananas (binary search on the answer). Any time you need the largest value not exceeding X in a sorted structure, reach for a floor binary search.

RUN IT Append on set; binary-search on get

operations

step 0 / 16

STARTTimeMap initialized. Ready to process operations.

1class TimeMap {
2  private store: Map<string, { ts: number; val: string }[]>;
3 
4▶  constructor() {
5▶    this.store = new Map();
6  }
7 
8  set(key: string, value: string, timestamp: number): void {
9    if (!this.store.has(key)) this.store.set(key, []);
10    this.store.get(key)!.push({ ts: timestamp, val: value });
11    // timestamps arrive in strictly increasing order — no sorting needed
12  }
13 
14  get(key: string, timestamp: number): string {
15    const list = this.store.get(key);
16    if (!list || list.length === 0) return '';
17 
18    // Binary search: find the largest ts <= timestamp
19    let lo = 0, hi = list.length - 1, ans = -1;
20    while (lo <= hi) {
21      const mid = Math.floor((lo + hi) / 2);
22      if (list[mid].ts <= timestamp) {
23        ans = mid;     // valid candidate; try to find a larger one on the right
24        lo = mid + 1;
25      } else {
26        hi = mid - 1;  // too large; look left
27      }
28    }
29    return ans === -1 ? '' : list[ans].val;
30  }
31}

State

{}

store

just inserted / active windowcurrent candidate (ts <= query)too large (discarded)answer found / exact match

slowfast

TYPESCRIPT The solution, annotated

timeMap.ts
class TimeMap {
  private store: Map<string, { ts: number; val: string }[]>;

  constructor() {
    this.store = new Map();
  }

  set(key: string, value: string, timestamp: number): void {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key)!.push({ ts: timestamp, val: value });
    // timestamps arrive in strictly increasing order — no sorting needed
  }

  get(key: string, timestamp: number): string {
    const list = this.store.get(key);
    if (!list || list.length === 0) return '';

    // Binary search: find the largest ts <= timestamp
    let lo = 0, hi = list.length - 1, ans = -1;
    while (lo <= hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (list[mid].ts <= timestamp) {
        ans = mid;     // valid candidate; try to find a larger one on the right
        lo = mid + 1;
      } else {
        hi = mid - 1;  // too large; look left
      }
    }
    return ans === -1 ? '' : list[ans].val;
  }
}

Reading it block by block

Lines 1–5 — storage shape. store maps each key to an array of { ts, val } pairs. One array per key, entries arriving in timestamp order.

Lines 7–10 — set. Lazily creates the array on first use, then appends. The problem guarantees timestamps are strictly increasing per key, so the array is always sorted — no sort call ever needed.

Lines 12–14 — get: early exit. If the key is unknown or the list is empty, return "" immediately.

Lines 16–22 — floor binary search. ans tracks the index of the best candidate seen so far. When list[mid].ts <= timestamp we have a valid candidate and push lo right to hunt for a larger valid one. When list[mid].ts > timestamp we pull hi left. After the loop ans holds the rightmost valid index, or -1 if none.

Line 23 — return. ans === -1 means all stored timestamps exceed the query — return "". Otherwise return the value at list[ans].val.

Complexity → set: O(1) amortized (array append). get: O(log n) per key list of length n. Total space: O(S) where S = total number of set calls.

INTERVIEWFollow-ups they'll ask

"What if timestamps are NOT strictly increasing?"You'd need to insert in sorted order (O(n) per insertion) or use a sorted data structure like a balanced BST / sorted map.
"Can you support delete(key, timestamp)?" Mark entries as deleted with a tombstone value, or switch to a sorted map that supports O(log n) removal.
"What if memory is tight and values repeat?" Deduplicate consecutive identical values — only store an entry when the value changes. The binary search logic stays identical.
"Return the timestamp alongside the value?" Just return list[ans] instead of list[ans].val.
"What's the brute force?" Iterate backward through the list and return the first entry whose ts is ≤ query. O(n) per get versus O(log n) here.

MNEMONIC The one-liner

"set just appends in time order — get binary-searches for the floor timestamp."

TRIGGERS When you see _ → reach for _

"most recent value at or before timestamp"	floor binary search on sorted list
set guarantees increasing timestamps	free sorted order → O(1) insert, O(log n) lookup
"design a versioned / time-traveling store"	Map<key, {ts,val}[]> + binary search
"largest X not exceeding Y" in sorted array	floor binary search (lo/hi/ans pattern)

SKELETON The reusable shape

skeleton.ts
class TimeMap {
  private store: Map<string, { ts: number; val: string }[]>;
  constructor() { this.store = new Map(); }

  set(key: string, value: string, timestamp: number): void {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key)!.push({ ts: timestamp, val: value });
  }

  get(key: string, timestamp: number): string {
    const list = this.store.get(key);
    if (!list || !list.length) return '';
    let lo = 0, hi = list.length - 1, ans = -1;
    while (lo <= hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (list[mid].ts <= timestamp) { ans = mid; lo = mid + 1; }
      else hi = mid - 1;
    }
    return ans === -1 ? '' : list[ans].val;
  }
}

FLASHCARDS Tap to flip

Why can we binary-search in get?

set is called with strictly increasing timestamps, so each key's list is automatically sorted.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What does get("love", 3) return after set("love", "10", 1) and set("love", "20", 2)?

QUESTION 02

What does get("love", 0) return after those same two set calls?

QUESTION 03

Time complexity of get per key list of length n?

QUESTION 04

Why does the binary search use <= rather than < when comparing list[mid].ts to the query?

QUESTION 05

Why does set not need to sort the list after each insertion?

QUESTION 06

If the binary search loop exits with ans still equal to -1, what should get return?

QUESTION 07

Which of these problems uses the same "floor in sorted array" binary search idea?

QUESTION 08

#981 · Time Based Key-Value StoreStore each key's values in an append-only list sorted by timestamp. A get query binary-searches for the largest timestamp ≤ the given time, giving O(log n) per operation.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Per-key sorted list + binary search

RECIPE Append on set, binary-search on get

COST Complexity & alternatives

RUN IT Append on set; binary-search on get

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _