320. Time Based Key-Value Store

Because set is called with strictly increasing timestamps, each key's (timestamp, value) entries are naturally sorted. A get is then a binary search for the largest timestamp <= the query.

Sorted by construction

Store, per key, a list of (timestamp, value) appended in call order. Since timestamps strictly increase, this list is already sorted by timestamp — no re-sorting needed.

A get(key, t) binary-searches for the rightmost entry whose timestamp is <= t:

set(key, value, ts): store[key].append((ts, value))
get(key, t):
    arr = store[key]
    i = bisect_right(arr, (t, +inf))
    return arr[i-1].value if i else ""

(In Java, a TreeMap<Integer,String> per key with floorKey does the same.)

Worked example

set('foo','bar',1); get('foo',1)='bar'; get('foo',3)='bar' (largest ts <= 3 is 1); set('foo','bar2',4); get('foo',5)='bar2'.

Complexity

• Time: set O(1), get O(log n).
• Space: O(n).

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

class TimeMap {
    private Map<String, TreeMap<Integer, String>> store = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, z -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tm = store.get(key);
        if (tm == null) return "";
        Integer floor = tm.floorKey(timestamp);
        return floor == null ? "" : tm.get(floor);
    }
}