LeetCode 981 · Medium · Binary Search

Time Based Key-Value Store

Design a map that keeps every version of a key. set(key, value, t) stores a value at time t; get(key, t) returns the value set most recently at or before t, or "" if there is none.

O(1) · O(log n)set · get
O(n)space
last t ≤ querybinary search per key

set key value t · get key t · separated by ; · 1–12 calls · key and value: 1–6 letters or digits · t: 1–99, set times strictly increasing

Calls pointer walks the calls · return value underneath

keyStore one list per key, oldest first: value in the box, timestamp underneath

class TimeMap { private static class Version { String value; int t; Version(String value, int t) { this.value = value; this.t = t; } } private Map<String, List<Version>> keyStore; public TimeMap() { keyStore = new HashMap<>(); // key -> list of versions } public void set(String key, String value, int timestamp) { if (!keyStore.containsKey(key)) { keyStore.put(key, new ArrayList<>()); } keyStore.get(key).add(new Version(value, timestamp)); } public String get(String key, int timestamp) { String res = ""; List<Version> values = keyStore.getOrDefault(key, new ArrayList<>()); int l = 0; int r = values.size() - 1; while (l <= r) { int m = l + (r - l) / 2; if (values.get(m).t <= timestamp) { res = values.get(m).value; // candidate; look later l = m + 1; } else { r = m - 1; } } return res; }}
call
—
l, r
—
m
—
res
—
returns
—

Why it works

  1. Brute force scans the key's whole history on every get and keeps the latest timestamp that is not after the query: O(n) per call.
  2. Key insight: the lists are already sorted. Set timestamps only increase, so appending keeps each key's list in time order for free. get wants the last entry with t ≤ timestamp: an "is it too late?" test that reads no, no, …, no, yes, yes. Binary search for the boundary, keeping the best "no" seen in res.
  3. O(1) set, O(log n) get, where n is the number of versions of that key. Space is O(total sets).
  4. Pitfall: stopping at an exact match is not enough. Most queries fall between two timestamps. On t ≤ timestamp, record the value and keep searching to the right; the loop ends on the last such version, exact match or not. A query earlier than every set, or an unknown key, returns "".
  5. In Java, a TreeMap<Integer, String> per key answers the same query with floorEntry(timestamp) in O(log n). It also copes with set times that arrive out of order, at O(log n) per set instead of O(1).