Time Based Key Value Store: the idea to remember.

The core insight

Append each key's timestamped values and binary search for the last timestamp not exceeding the query.

Why it works

Increasing timestamps keep each history sorted, so the upper bound separates usable versions from future versions.

The mistake to avoid

Return an empty string when the key is absent or the query precedes its earliest version.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Append each key's timestamped values and binary search for the last timestamp not exceeding the query.
class TimeMap {

    HashMap<String, List<Pair<String, Integer>>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) map.put(key, new ArrayList<>());
        map.get(key).add(new Pair(value, timestamp));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";
        List<Pair<String, Integer>> list = map.get(key);
        return search(list, timestamp);
    }

    public String search(List<Pair<String, Integer>> list, int timestamp) {
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            int mid = start + (end - start + 1) / 2;
            if (list.get(mid).getValue() <= timestamp) start = mid; else end =
                mid - 1;
        }
        return list.get(start).getValue() <= timestamp
            ? list.get(start).getKey()
            : "";
    }
}

// Small standard-Java replacement for the platform Pair helper.
static class Pair<K,V> {
    final K key; final V value;
    Pair(K key,V value) { this.key=key; this.value=value; }
    K getKey() { return key; }
    V getValue() { return value; }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection