33.Time Based Key-Value Store

MediumBinary Search · 6/7

Problem

Design a time-based key-value store that can keep multiple values for the same key at different timestamps and return the value that was current at a given time.

Implement TimeMap:

TimeMap() initializes the store.
void set(String key, String value, int timestamp) stores value for key at time timestamp.
String get(String key, int timestamp) returns the value set for key at the largest timestamp prev with prev <= timestamp. If there is none, return "".

Examples

Input:
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output:
[null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation:
set("foo", "bar", 1)
get("foo", 1) → "bar"   (exact match at 1)
get("foo", 3) → "bar"   (no value at 3; latest before it is at 1)
set("foo", "bar2", 4)
get("foo", 4) → "bar2"
get("foo", 5) → "bar2"

Input:
["TimeMap", "set", "get", "get"]
[[], ["love", "high", 10], ["love", 5], ["love", 10]]
Output:
[null, null, "", "high"]
Explanation: At time 5 nothing had been stored for "love" yet, so the answer is "".

Constraints

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

💡 Key Insight

Because set is always called with increasing timestamps, simply appending to a per-key list keeps that list sorted by timestamp for free. A get then becomes "find the last entry with time <= timestamp" — a classic upper-bound binary search on that list, in O(log n).

Brute Force (Linear Scan)

Timeset O(1) amortized; get O(n) where n is the number of values stored for that key.SpaceO(N)

Intuition

Store, for each key, a list of (timestamp, value) pairs in insertion order. For get, walk the list backwards and return the first pair whose timestamp is <= timestamp.

Algorithm

set: append (timestamp, value) to map[key].
get: if key is missing return "". Otherwise iterate from the last pair to the first; return the value of the first pair with time <= timestamp.
If none qualifies, return "".

Visualization

map["foo"] = [(1,"bar"), (4,"bar2")]

get("foo", 3):  (4,"bar2") 4 > 3 ✗  →  (1,"bar") 1 ≤ 3 ✓  → "bar"

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {
    private static class TimeValue {
        final int time;
        final String value;

        TimeValue(int time, String value) {
            this.time = time;
            this.value = value;
        }
    }

    private final Map<String, List<TimeValue>> store;

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

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new TimeValue(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<TimeValue> list = store.get(key);
        if (list == null) {
            return "";
        }
        // newest first: the first match is the latest time <= timestamp
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i).time <= timestamp) {
                return list.get(i).value;
            }
        }
        return "";
    }
}

Complexity

Time: set O(1) amortized; get O(n) where n is the number of values stored for that key.
Space: O(N) — one entry per set call.

TreeMap Floor Lookup

Timeset O(log n); get O(log n).SpaceO(N)

Intuition

A TreeMap<Integer, String> per key keeps timestamps sorted in a balanced BST. Its floorEntry(timestamp) returns exactly "the greatest key <= timestamp" — the definition of get. This also works even if timestamps were not increasing.

Algorithm

set: map[key].put(timestamp, value).
get: if key is missing return ""; else e = map[key].floorEntry(timestamp); return e == null ? "" : e.getValue().

Visualization

tree for "foo":        1 → "bar"
                         \
                          4 → "bar2"

floorEntry(3) → walks: 1 (≤3, candidate) → 4 (>3, go left: null) → answer key 1 → "bar"

Code

java

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

class TimeMap {
    private final Map<String, TreeMap<Integer, String>> store;

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

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

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tree = store.get(key);
        if (tree == null) {
            return "";
        }
        Map.Entry<Integer, String> entry = tree.floorEntry(timestamp); // greatest time <= timestamp
        return entry == null ? "" : entry.getValue();
    }
}

Complexity

Time: set O(log n); get O(log n).
Space: O(N) — but tree nodes carry more overhead (boxed keys, parent/child pointers, color bits) than a plain list.

HashMap + Sorted List + Binary SearchOptimal

Timeset O(1) amortized; get O(log n) for the n values of that key.SpaceO(N)

Intuition

Exploit the guarantee that set timestamps strictly increase: appending to an ArrayList keeps it sorted, so set is O(1). For get, binary-search the list for the rightmost entry with time <= timestamp. Whenever list[mid].time <= timestamp, mid is a valid candidate — remember it and look further right for a later one; otherwise look left.

Algorithm

set: append (timestamp, value) to map[key].
get: if key is missing return "".
lo = 0, hi = size - 1, res = "".
While lo <= hi:
- mid = lo + (hi - lo) / 2.
- If list[mid].time <= timestamp: res = list[mid].value, lo = mid + 1.
- Else hi = mid - 1.
Return res.

Dry Run

flowchart TD
    A["list for 'k' = [(1,a), (3,b), (6,c), (9,d)]<br/>get('k', 7): lo=0, hi=3, res=''"] --> B["mid=1: time 3 ≤ 7"]
    B -->|"res=b, go right"| C["lo=2, hi=3"]
    C --> D["mid=2: time 6 ≤ 7"]
    D -->|"res=c, go right"| E["lo=3, hi=3"]
    E --> F["mid=3: time 9 > 7"]
    F -->|"go left"| G["lo=3, hi=2 → stop"]
    G --> H["return 'c'"]

Code

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {
    private static class TimeValue {
        final int time;
        final String value;

        TimeValue(int time, String value) {
            this.time = time;
            this.value = value;
        }
    }

    private final Map<String, List<TimeValue>> store;

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

    public void set(String key, String value, int timestamp) {
        // timestamps arrive in increasing order, so appending keeps the list sorted
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new TimeValue(timestamp, value));
    }

    public String get(String key, int timestamp) {
        List<TimeValue> list = store.get(key);
        if (list == null) {
            return "";
        }
        String res = "";
        int lo = 0;
        int hi = list.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid).time <= timestamp) {
                res = list.get(mid).value; // valid candidate; try to find a later one
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }
}

Complexity

Time: set O(1) amortized; get O(log n) for the n values of that key.
Space: O(N) — one compact entry per set call.

Complexity Comparison

Approach	Time	Space
Linear Scan	set O(1), get O(n)	O(N)
TreeMap Floor Lookup	set O(log n), get O(log n)	O(N)
HashMap + Binary Search	set O(1), get O(log n)	O(N)

Common Pitfalls

Returning null instead of "" when the key is missing or every stored timestamp is larger than the query.
Doing an exact-match binary search — the query timestamp often falls between stored timestamps; you need the floor, not equality.
Stopping the binary search at the first time <= timestamp hit — there may be a later valid entry to its right; keep moving lo = mid + 1.
Using TreeMap.floorKey and then a second get — it works but does two O(log n) lookups; floorEntry returns both at once.
Relying on the sorted-append trick when timestamps are not guaranteed to increase — then you need the TreeMap version.