Time Based Key-Value Store

MediumDesign · Hash Map · Binary Search🧩 Data Structure Design LeetCode #981 ↗Updated Oct 30, 2026

Problem

Design a TimeMap that keeps every version of a key. set(key, value, timestamp) records a value at a time, and get(key, timestamp) returns the value stored with the largest timestamp ≤ the given one, or "" if there is none. Timestamps passed to set are strictly increasing.

Inputset("foo","bar",1); get("foo",1); get("foo",3)Output"bar", "bar"

Inputset("foo","bar2",4); get("foo",4); get("foo",5)Output"bar2", "bar2"

Inputget("foo",0)Output"" (nothing at or before time 0)

1 ≤ key, value length ≤ 100 · 1 ≤ timestamp ≤ 10⁷ · set timestamps strictly increasing · ≤ 2·10⁵ calls

Try it yourself

Java

class TimeMap {
    public TimeMap() {
        
    }

    public void set(String key, String value, int timestamp) {
        
    }

    public String get(String key, int timestamp) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Because set timestamps only grow, appending to a per-key list keeps that list already sorted by time. A query is then “last entry with time ≤ t” — a binary search, with no tree or sorting needed.

PatternData Structure Design

Instinct Implement a class whose methods must all hit a time bound (often O(1)) - write each method's target cost, then glue a hash map to a structure that keeps order.

Memory hack Finder plus keeper - a hash map finds it fast, a list/heap/array keeps the order, and every method updates both.

Open the Data Structure Design guide →

Approaches

Brute ForcePer-Key History + Backward Scan

Time set O(1), get O(k)Space O(total sets)

Keep a list of (time, value) entries per key in insertion order. To answer get, walk the list from the newest entry backwards and return the first one whose time is not after the query time.

Java

class TimeMap {
    private class Entry {
        final int time; final String value;
        Entry(int t, String v) { time = t; value = v; }
    }
    private final Map<String, List<Entry>> map = new HashMap<>();
    public TimeMap() { }
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Entry(timestamp, value));
    }
    public String get(String key, int timestamp) {
        List<Entry> list = map.getOrDefault(key, Collections.emptyList());
        for (int i = list.size() - 1; i >= 0; i--) { // newest first
            if (list.get(i).time <= timestamp) return list.get(i).value;
        }
        return "";
    }
}

Simple and correct, but a key with many versions makes every lookup linear (k = versions of that key).

BetterHashMap of TreeMaps (floorEntry)

Time set O(log k), get O(log k)Space O(total sets)

Give each key its own TreeMap<time, value>. A balanced tree answers “greatest key ≤ t” directly with floorEntry, and it would still work if timestamps arrived out of order.

Java

class TimeMap {
    private final Map<String, TreeMap<Integer, String>> map = new HashMap<>();
    public TimeMap() { }
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> versions = map.get(key);
        if (versions == null) return "";
        Map.Entry<Integer, String> e = versions.floorEntry(timestamp); // latest time <= t
        return e == null ? "" : e.getValue();
    }
}

Logarithmic both ways and robust, but pays tree overhead the sorted input never needed.

OptimalAppend-Only Lists + Binary Search

Time set O(1), get O(log k)Space O(total sets)

Strictly increasing timestamps mean each per-key list is sorted just by appending. get binary searches for the last entry with time ≤ t; if even the first entry is later than t, the answer is empty.

Java

class TimeMap {
    private class Entry {
        final int time; final String value;
        Entry(int t, String v) { time = t; value = v; }
    }
    private final Map<String, List<Entry>> map = new HashMap<>();
    public TimeMap() { }
    public void set(String key, String value, int timestamp) {
        // timestamps only grow, so appending keeps each list sorted
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Entry(timestamp, value));
    }
    public String get(String key, int timestamp) {
        List<Entry> list = map.get(key);
        if (list == null || list.get(0).time > timestamp) return "";
        int lo = 0, hi = list.size() - 1; // find last entry with time <= timestamp
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2; // round up so lo = mid always progresses
            if (list.get(mid).time <= timestamp) lo = mid;
            else hi = mid - 1;
        }
        return list.get(lo).value;
    }
}

Constant-time writes, logarithmic reads, and compact arrays — the best fit for the guarantees given.

Pro tip

When the search keeps lo = mid, round mid up; otherwise a two-element window loops forever.

At a glance

Level	Approach	Time	Space
Brute Force	Per-Key History + Backward Scan	`set O(1), get O(k)`	`O(total sets)`
Better	HashMap of TreeMaps (floorEntry)	`set O(log k), get O(log k)`	`O(total sets)`
Optimal	Append-Only Lists + Binary Search	`set O(1), get O(log k)`	`O(total sets)`

Common pitfalls

Returning null instead of "" for an unknown key or too-early time.
Binary searching for an exact match and missing the “floor” semantics.
Rounding mid down with lo = mid — an infinite loop on two elements.

Interview tips

Ask whether timestamps are increasing — it decides list vs. tree.
Name the query precisely: last version at or before t (a floor search).
Offer the TreeMap version as the fallback for out-of-order writes.

Pattern

Versioned values + binary search → “what was the value as of time t” over append-only, time-ordered data.

My notes saved in this browser