Time Based Key-Value Store

Description

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

TimeMap() — Initializes the object.
void set(String key, String value, int timestamp) — Stores the key key with the value value at the given timestamp.
String get(String key, int timestamp) — Returns a value such that set was called previously with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If no value exists, return "".

Important constraint: All timestamps passed to set are strictly increasing. This means for any given key, the values are stored in chronological order.

Examples

Example 1

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:

TimeMap() — Initialize.
set("foo", "bar", 1) — Store "bar" for key "foo" at timestamp 1.
get("foo", 1) → "bar" — Timestamp 1 exists for "foo", return its value.
get("foo", 3) → "bar" — No value at timestamp 3, but timestamp 1 ≤ 3, so return "bar" (the latest value at or before time 3).
set("foo", "bar2", 4) — Store "bar2" for key "foo" at timestamp 4.
get("foo", 4) → "bar2" — Exact match at timestamp 4.
get("foo", 5) → "bar2" — Timestamp 4 ≤ 5, and it's the latest, so return "bar2".

Example 2

Input:

["TimeMap", "set", "set", "set", "get", "get", "get"]
[[], ["user", "active", 1], ["user", "away", 3], ["user", "offline", 7], ["user", 0], ["user", 5], ["user", 10]]

Output: [null, null, null, null, "", "away", "offline"]

Explanation:

Store three values for "user": "active" at t=1, "away" at t=3, "offline" at t=7.
get("user", 0) → "" — No timestamp ≤ 0 exists.
get("user", 5) → "away" — Timestamps 1 and 3 are both ≤ 5. The largest is 3, which has value "away".
get("user", 10) → "offline" — Timestamp 7 is the largest ≤ 10.

Constraints

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

Editorial

Brute Force - Linear Search

Intuition

Let's start with the simplest data structure design. We need to:

Store multiple (timestamp, value) pairs per key.
Retrieve the value with the largest timestamp ≤ a query timestamp.

A hash map naturally handles the "per key" part: map each key to a list of (timestamp, value) entries. Since timestamps come in strictly increasing order, the list is automatically sorted by time — no manual sorting needed.

For set: just append the new (timestamp, value) to the key's list. O(1).

For get: scan the list backwards (from most recent to oldest) and return the first entry whose timestamp ≤ the query. This works because the list is sorted — the first match from the end is the largest valid timestamp.

Think of it like checking a revision history: you start from the latest revision and scroll backward until you find one that was created before your deadline.

Step-by-Step Explanation

Let's trace the operations: set("foo", "bar", 1), set("foo", "bar2", 4), set("foo", "bar3", 7), then get("foo", 5).

Step 1: set("foo", "bar", 1). Append (1, "bar") to foo's list.

Map: {"foo": [(1, "bar")]}

Step 2: set("foo", "bar2", 4). Append (4, "bar2").

Map: {"foo": [(1, "bar"), (4, "bar2")]}

Step 3: set("foo", "bar3", 7). Append (7, "bar3").

Map: {"foo": [(1, "bar"), (4, "bar2"), (7, "bar3")]}

Step 4: get("foo", 5). Scan foo's list backward:

Check index 2: timestamp 7. Is 7 ≤ 5? No. Move left.
Check index 1: timestamp 4. Is 4 ≤ 5? YES! Return "bar2".

We checked 2 entries before finding the answer. In the worst case, we'd scan all entries.

Linear Search — Scanning Backwards for Latest Valid Timestamp — Watch how the get operation scans the timestamp list from right to left, finding the most recent entry that doesn't exceed the query timestamp.

Now let's also trace the worst case: get("foo", 0).

Step 1: Scan index 2: timestamp 7 > 0. Skip.
Step 2: Scan index 1: timestamp 4 > 0. Skip.
Step 3: Scan index 0: timestamp 1 > 0. Skip.
Step 4: Exhausted the list. Return "".

We checked all 3 entries to conclude that no valid value exists. This is the O(n) worst case.

Algorithm

Data Structure: Hash map where each key maps to a list of (timestamp, value) pairs.

set(key, value, timestamp):

Append (timestamp, value) to the list for key.

get(key, timestamp):

If key doesn't exist in the map, return "".
Get the list of entries for key.
Iterate from the last entry to the first:
- If the entry's timestamp ≤ timestamp, return its value.
If no entry found, return "".

Code

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";

        auto& entries = store[key];
        for (int i = entries.size() - 1; i >= 0; i--) {
            if (entries[i].first <= timestamp) {
                return entries[i].second;
            }
        }
        return "";
    }
};

from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""

        entries = self.store[key]
        for i in range(len(entries) - 1, -1, -1):
            if entries[i][0] <= timestamp:
                return entries[i][1]
        return ""

class TimeMap {
    private Map<String, List<int[]>> store;
    private Map<String, List<String>> valueStore;

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

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

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) return "";

        List<int[]> times = store.get(key);
        List<String> values = valueStore.get(key);

        for (int i = times.size() - 1; i >= 0; i--) {
            if (times.get(i)[0] <= timestamp) {
                return values.get(i);
            }
        }
        return "";
    }
}

Complexity Analysis

Time Complexity:

set: O(1) — append to a list and hash map insertion are both amortized constant.
get: O(n) where n is the number of entries for the given key. In the worst case, we scan every entry (e.g., querying a timestamp smaller than all stored timestamps).

With up to 2 × 10^5 calls, if most are get operations on keys with many entries, the total time could reach O(n²) across all operations.

Space Complexity: O(m) where m is the total number of set calls. Each call stores one (timestamp, value) pair in the hash map.

Why This Approach Is Not Efficient

The linear scan for get is O(n) per call, where n is the number of timestamps stored for that key. With up to 2 × 10^5 calls and keys potentially having thousands of entries, this becomes a bottleneck.

But we're missing a crucial observation: the list is already sorted by timestamp (since timestamps arrive in strictly increasing order). We're treating a sorted list as if it were unsorted — scanning linearly when we could jump.

Whenever you need to find a value in a sorted collection, binary search is the tool. Instead of checking entries one by one (O(n)), binary search halves the search space at each step, giving O(log n) per get call.

For a key with 100,000 entries: linear search checks up to 100,000 entries; binary search checks at most 17.

Optimal Approach - Binary Search

Intuition

The data structure stays the same: a hash map where each key maps to a list of (timestamp, value) pairs. The set operation is identical — just append.

The improvement is entirely in get. Since the timestamp list is sorted in increasing order, we can use binary search to find the rightmost timestamp ≤ the query.

Specifically, we want to find the largest timestamp that is ≤ query timestamp. This is equivalent to finding the rightmost position where we could insert query_timestamp while maintaining sorted order, then looking at the element just before that position.

Think of a phone book sorted by name. To find "Smith", you don't read every name from A to Z. You open to the middle, check if "Smith" comes before or after, then repeat on the correct half. Each step eliminates half the remaining entries.

Step-by-Step Explanation

Let's trace get("foo", 5) with entries: [(1, "bar"), (3, "bar2"), (5, "bar3"), (8, "bar4"), (12, "bar5")].
Timestamps: [1, 3, 5, 8, 12]. Find the largest timestamp ≤ 5.

Step 1: Initialize left = 0, right = 4, result = -1.

Step 2: mid = (0 + 4) / 2 = 2. Timestamp at index 2 = 5. Is 5 ≤ 5? YES. Update result = 2. Search right half for a potentially larger valid timestamp: left = 3.

Step 3: mid = (3 + 4) / 2 = 3. Timestamp at index 3 = 8. Is 8 ≤ 5? NO. Search left half: right = 2.

Step 4: left (3) > right (2). Loop ends. result = 2.

Step 5: Return entries[2].value = "bar3".

We checked only 2 entries out of 5. Binary search eliminated half the list at each step.

Binary Search — Finding the Rightmost Timestamp ≤ Query — Watch how binary search narrows the search range by half at each step, efficiently finding the largest timestamp that doesn't exceed our query.

Algorithm

Data Structure: Hash map where each key maps to a list of (timestamp, value) pairs (same as brute force).

set(key, value, timestamp):

Append (timestamp, value) to the list for key. (Identical to brute force.)

get(key, timestamp):

If key doesn't exist, return "".
Get the list of entries for key.
Binary search for the largest timestamp ≤ timestamp:
a. Initialize left = 0, right = len(entries) - 1, result = -1.
b. While left ≤ right:
- mid = (left + right) / 2
- If entries[mid].timestamp ≤ timestamp: update result = mid, move left = mid + 1 (search for larger).
- Else: move right = mid - 1 (search for smaller).
If result ≥ 0, return entries[result].value. Otherwise return "".

Code

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";

        auto& entries = store[key];
        int left = 0, right = entries.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (entries[mid].first <= timestamp) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result >= 0 ? entries[result].second : "";
    }
};

from collections import defaultdict
from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""

        entries = self.store[key]
        # bisect_right finds insertion point after all entries ≤ timestamp
        idx = bisect_right(entries, (timestamp, chr(127)))
        return entries[idx - 1][1] if idx > 0 else ""

class TimeMap {
    private Map<String, List<int[]>> timeStore;
    private Map<String, List<String>> valStore;

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

    public void set(String key, String value, int timestamp) {
        timeStore.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        valStore.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        if (!timeStore.containsKey(key)) return "";

        List<int[]> times = timeStore.get(key);
        List<String> values = valStore.get(key);
        int left = 0, right = times.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (times.get(mid)[0] <= timestamp) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result >= 0 ? values.get(result) : "";
    }
}

Complexity Analysis

Time Complexity:

set: O(1) — append and hash map insertion, both amortized constant.
get: O(log n) where n is the number of entries for the given key. Binary search halves the search space at each step: checking at most ⌈log₂(n)⌉ entries. For n = 200,000 entries, that's at most 18 comparisons.

Space Complexity: O(m) where m is the total number of set calls. Each stores one (timestamp, value) pair. The binary search uses O(1) extra space (just a few pointer variables).

Comparison:

Operation	Brute Force	Binary Search
`set`	O(1)	O(1)
`get`	O(n)	O(log n)
Space	O(m)	O(m)

The set operation is identical in both approaches. The entire improvement comes from replacing O(n) linear scan with O(log n) binary search in get. This is made possible by the guarantee that timestamps arrive in increasing order, keeping the list sorted without extra work.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Time Based Key-Value Store

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force - Linear Search

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Binary Search

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis