981. Time Based Key-Value Store

Design a time-based key-value store. set(key, value, timestamp) stores a value; get(key, timestamp) returns the value with the largest stored timestamp ≤ timestamp, or "". Timestamps passed to set are strictly increasing.

Each key's history is already sorted by timestamp. Binary search for the last timestamp ≤ the query.

1class TimeMap {
2  store = new Map<string, [number, string][]>();
3  set(key: string, value: string, timestamp: number): void {
4    if (!this.store.has(key)) this.store.set(key, []);
5    this.store.get(key)!.push([timestamp, value]);
6  }
7  get(key: string, timestamp: number): string {
8    const hist = this.store.get(key) ?? [];
9    let lo = 0, hi = hist.length - 1, ans = "";
10    while (lo <= hi) {
11      const mid = (lo + hi) >> 1;
12      if (hist[mid][0] <= timestamp) { ans = hist[mid][1]; lo = mid + 1; }
13      else hi = mid - 1;
14    }
15    return ans;
16  }
17}

op = TimeMap()

output

null

Empty store.

1 / 0

Space: play/pause · ←/→: step