Problem statement

Build a key-value store that remembers every value a key has ever held, each stamped with the time it was written, and can answer "what was this key's value at time t?".

Write the class TimeMap:

• TimeMap() creates an empty store.
• void set(String key, String value, int timestamp) records that key holds value from time timestamp on.
• String get(String key, int timestamp) returns the value of the set call for key with the largest timestamp that is <= timestamp. If key was never set at or before that time, it returns the empty string "".

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["TimeMap","set","get","get","set","get","get"]
[[],["fruit","apple",1],["fruit",1],["fruit",3],["fruit","mango",4],["fruit",4],["fruit",5]]
Output: [null,null,"apple","apple",null,"mango","mango"]
Explanation: At times 1 and 3 the latest value of fruit is apple. From time 4 on, mango replaces it.

Example 2

Input: ["TimeMap","set","set","get","get","get"]
[[],["k1","low",10],["k2","high",20],["k1",9],["k2",25],["k3",30]]
Output: [null,null,null,"","high",""]
Explanation: k1 was first set at time 10, so asking at time 9 gives the empty string. k2 at time 25 is high; k3 was never set.

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits
• 1 <= timestamp <= 10^7
• The timestamps of all set calls are strictly increasing
• At most 2 * 10^5 calls are made to set and get

Hints for Time Based Key-Value Store

1. Hint 1

   Group the history by key: each key needs its own list of (timestamp, value) pairs.

2. Hint 2

   Because the set timestamps only ever increase, appending to a key's list keeps it sorted by time — no sorting needed.

3. Hint 3

   get wants the last entry with time <= timestamp: binary search the key's list for the first time greater than timestamp and step back one. If that falls before the start, answer "".

How to solve Time Based Key-Value Store

A hash map from key to that key's history. The histories are appended in time order, so each one is already sorted and a binary search finds the value in force at any time.

Approach

1. set(key, value, timestamp): append (timestamp, value) to history[key].
2. get(key, timestamp): if key has no history, return "".
3. Binary search the history for the first entry whose time is greater than timestamp; the entry just before it is the latest one at or before timestamp.
4. Return that entry's value, or "" if there is none (every write came later).

Why it works

The problem guarantees strictly increasing set timestamps, so every history list is sorted by time by construction. In a sorted list the entries <= timestamp form a prefix; its last element is the most recent write that had happened by then, which is exactly the value the key held.

Complexity

• Time — O(1) per set, O(log m) per get for a key with m writes
• Space — O(total number of set calls)

Pitfalls

• Searching for the first time >= timestamp and stepping back one skips a write made exactly at timestamp, which must be returned.
• A key that exists but whose first write is after timestamp must give "", not its first value.
• Scanning the whole list on every get is O(m) and too slow at 2 × 10^5 calls.

Reference solution

Python

import bisect

class TimeMap:

    def __init__(self):
        self.times = {}
        self.values = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # set timestamps only increase, so each list stays sorted
        self.times.setdefault(key, []).append(timestamp)
        self.values.setdefault(key, []).append(value)

    def get(self, key: str, timestamp: int) -> str:
        ts = self.times.get(key)
        if not ts:
            return ""
        i = bisect.bisect_right(ts, timestamp) - 1
        return self.values[key][i] if i >= 0 else ""

Java

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

    public TimeMap() {
    }

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

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> t = h.get(key);
        if (t == null) return "";
        Map.Entry<Integer, String> e = t.floorEntry(timestamp); // latest write at or before timestamp
        return e == null ? "" : e.getValue();
    }
}

C++

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> h;
public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        h[key].push_back({timestamp, value}); // set timestamps only increase
    }

    string get(string key, int timestamp) {
        auto it = h.find(key);
        if (it == h.end()) return "";
        auto& v = it->second;
        auto p = upper_bound(v.begin(), v.end(), timestamp,
            [](int t, const pair<int, string>& e) { return t < e.first; });
        return p == v.begin() ? "" : prev(p)->second;
    }
};

JavaScript

var TimeMap = function() {
    this.h = new Map(); // key -> { ts: [], vs: [] }, sorted by time
};

TimeMap.prototype.set = function(key, value, timestamp) {
    var e = this.h.get(key);
    if (!e) { e = { ts: [], vs: [] }; this.h.set(key, e); }
    e.ts.push(timestamp);
    e.vs.push(value);
};

TimeMap.prototype.get = function(key, timestamp) {
    var e = this.h.get(key);
    if (!e) return "";
    var lo = 0, hi = e.ts.length; // first time > timestamp
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (e.ts[mid] <= timestamp) lo = mid + 1; else hi = mid;
    }
    return lo > 0 ? e.vs[lo - 1] : "";
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium