Log inSign up
mediumLeetCodeNot Started

Time Based Key-Value Store

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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

Implement the TimeMap class: - TimeMap(): Initializes the object of the data structure. - void set(String key, String value, int timestamp): Stores the key key with the value value at the given time 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 there are no values, it returns "".

Example 1 · 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 timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

Constraints:

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 107
  • All the timestamps of set are strictly increasing for any given key.
  • At most 2 * 105 calls will be made to set and get.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Time Based Key-Value Store.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Time Based Key-Value Store
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Basic prototyping when the number of entries is minimal.
  • BETTER: When get queries predominantly query the latest or very recent timestamps.
  • OPTIMAL: Optimal for production and large query volumes up to 2 * 105 operations.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Global List with Linear Scan

Intuition

Append all records (key, value, timestamp) to a central array. When get(key, timestamp) is requested, scan the list (or iterate backwards) to find the entry matching key with the greatest timestamp <= requested timestamp. Because the list contains up to N entries, each get operation requires O(N) time.

When to apply: Basic prototyping when the number of entries is minimal.

Algorithm

  1. Step 1: Store entries as objects { key, value, timestamp } in an array.
  2. Step 2: On set, push the new entry to the array.
  3. Step 3: On get, iterate through entries, tracking the best matching value whose timestamp is <= target.
  4. Step 4: Return the best found value, or empty string if none match.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4
5struct Entry {
6 std::string key;
7 std::string val;
8 int timestamp;
9};
10
11class TimeMapBrute {
12 std::vector<Entry> entries;
13public:
14 TimeMapBrute() {}
15
16 void set(const std::string& key, const std::string& value, int timestamp) {
17 entries.push_back({key, value, timestamp});
18 }
19
20 std::string get(const std::string& key, int timestamp) {
21 std::string res = "";
22 int bestTime = -1;
23 for (const auto& e : entries) {
24 if (e.key == key && e.timestamp <= timestamp && e.timestamp > bestTime) {
25 bestTime = e.timestamp;
26 res = e.val;
27 }
28 }
29 return res;
30 }
31};
32
33int main() {
34 TimeMapBrute tm;
35 tm.set("foo", "bar", 1);
36 std::cout << tm.get("foo", 1) << std::endl;
37 std::cout << tm.get("foo", 3) << std::endl;
38 tm.set("foo", "bar2", 4);
39 std::cout << tm.get("foo", 4) << std::endl;
40 std::cout << tm.get("foo", 5) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(1) for set, O(N) for get where N is total set calls
  • Space complexity: O(N) for storing entries

2. Hash Map of Key to Bucket with Reverse Linear Scan

Intuition

Organize records by mapping each key to an array of (timestamp, value) pairs in a hash map. Because timestamps are added chronologically, scanning backward from the end of the bucket allows finding the first timestamp <= query timestamp. In the best case, it terminates in O(1) if the query timestamp is current. However, in the worst case (query timestamp is smaller than all or earlier in time), it still takes O(M) time where M is the number of values stored for that key.

When to apply: When get queries predominantly query the latest or very recent timestamps.

Algorithm

  1. Step 1: Map key to an array of { timestamp, value } pairs.
  2. Step 2: On set, append { timestamp, value } to map[key].
  3. Step 3: On get, retrieve the array for key. If absent, return empty string.
  4. Step 4: Iterate backwards from the end of the array; return the first value where timestamp <= target.
  5. Step 5: If no such entry exists, return empty string.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5
6class TimeMapBetter {
7 std::unordered_map<std::string, std::vector<std::pair<int, std::string>>> store;
8public:
9 TimeMapBetter() {}
10
11 void set(const std::string& key, const std::string& value, int timestamp) {
12 store[key].push_back({timestamp, value});
13 }
14
15 std::string get(const std::string& key, int timestamp) {
16 auto it = store.find(key);
17 if (it == store.end()) return "";
18 const auto& list = it->second;
19 for (int i = (int)list.size() - 1; i >= 0; --i) {
20 if (list[i].first <= timestamp) {
21 return list[i].second;
22 }
23 }
24 return "";
25 }
26};
27
28int main() {
29 TimeMapBetter tm;
30 tm.set("foo", "bar", 1);
31 std::cout << tm.get("foo", 1) << std::endl;
32 std::cout << tm.get("foo", 3) << std::endl;
33 tm.set("foo", "bar2", 4);
34 std::cout << tm.get("foo", 4) << std::endl;
35 std::cout << tm.get("foo", 5) << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(1) for set, O(M) worst case for get where M is entries for that key
  • Space complexity: O(N) total space

3. Hash Map + Binary Search (upper_bound / bisect)

Intuition

Because the problem specifies that timestamps are strictly increasing for every call to set, appending new pairs (timestamp, value) keeps each key's list strictly sorted by timestamp automatically. To retrieve the largest timestamp <= query timestamp: 1. Lookup the list of pairs for the given key. If none, return "". 2. Binary search on the list: - Search for the upper bound of timestamp (the first entry with time > timestamp). - If that iterator is at the beginning (index 0), all recorded timestamps are strictly greater than the query, so return "". - Otherwise, the preceding index (idx - 1) represents the greatest timestamp <= query timestamp! Return its associated value. 3. Both operations achieve optimal performance: set in O(1), and get in O(log M) time.

When to apply: Optimal for production and large query volumes up to 2 * 105 operations.

Algorithm

  1. Step 1: Map key to an array of pairs (timestamp, value).
  2. Step 2: On set, push (timestamp, value) to map[key] in O(1) time.
  3. Step 3: On get, locate the pair array for key in O(1). If absent, return empty string.
  4. Step 4: Binary search for the rightmost entry where entry.timestamp <= timestamp in O(log M) time.
  5. Step 5: If a valid index is found, return its value; else return empty string.

Interactive trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
set('foo', 'bar', 1): Append { timestamp: 1, value: 'bar' } to store['foo']
Visual state
Values and pointers at this exact step
pointers
S
1
0
Check / comparison
Timestamps array: [1]
Decision / next transition
store['foo'] = [{t: 1, v: 'bar'}]
Why this step matters

set(foo, bar, 1): Append { timestamp: 1, value: bar } to store[foo].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4#include <unordered_map>
5#include <algorithm>
6
7class TimeMap {
8 std::unordered_map<std::string, std::vector<std::pair<int, std::string>>> store;
9public:
10 TimeMap() {}
11
12 void set(const std::string& key, const std::string& value, int timestamp) {
13 store[key].emplace_back(timestamp, value);
14 }
15
16 std::string get(const std::string& key, int timestamp) {
17 auto it = store.find(key);
18 if (it == store.end()) return "";
19
20 const auto& list = it->second;
21 // Binary search: upper_bound on timestamp
22 int left = 0, right = (int)list.size() - 1;
23 std::string ans = "";
24
25 while (left <= right) {
26 int mid = left + (right - left) / 2;
27 if (list[mid].first <= timestamp) {
28 ans = list[mid].second;
29 left = mid + 1; // look for larger timestamp <= query
30 } else {
31 right = mid - 1;
32 }
33 }
34
35 return ans;
36 }
37};
38
39int main() {
40 TimeMap tm;
41 tm.set("foo", "bar", 1);
42 std::cout << tm.get("foo", 1) << std::endl;
43 std::cout << tm.get("foo", 3) << std::endl;
44 tm.set("foo", "bar2", 4);
45 std::cout << tm.get("foo", 4) << std::endl;
46 std::cout << tm.get("foo", 5) << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(1) for set, O(log M) for get where M is the number of timestamps for the key
  • Space complexity: O(N) total space to store all key-timestamp-value entries

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Global List with Linear ScanO(1) for set, O(N) for get where N is total set callsO(N) for storing entriesStore all set operations in a flat list and scan backwards to find the largest timestamp <= query.O(1) for set, O(N) for get where N is total set calls
2.Hash Map of Key to Bucket with Reverse Linear ScanO(1) for set, O(M) worst case for get where M is entries for that keyO(N) total spaceBucket entries by key in a hash map. For get, scan backwards from the end of the key's list.O(1) for set, O(M) worst case for get where M is entries for that key
3.Hash Map + Binary Search (upper_bound / bisect)OptimalO(1) for set, O(log M) for get where M is the number of timestamps for the keyO(N) total space to store all key-timestamp-value entriesStore values in sorted order by timestamp per key. Use binary search to locate the predecessor timestamp in O(log M) time.O(1) for set, O(log M) for get where M is the number of timestamps for the key

Common Pitfalls & Crucial Edge Cases

Linear search in `get`

Scanning backwards takes O(N) worst case and causes TLE when there are thousands of timestamps for a key.

Using a `std::map<int, string>` in C++

While std::map gives O(log N) lookups, its red-black tree incurs higher memory overhead and cache misses than std::vector<pair<int, string>> with binary search.

Off-by-one in binary search

Forgetting that upper_bound returns the first element strictly greater, so the target is it - 1.

Crucial Edge Cases to Validate:

  • Key does not exist — Returns empty string "".
  • Query timestamp is smaller than all stored timestamps for the key — Returns empty string "".
  • Exact match with a stored timestamp — Returns the value at that exact timestamp.
  • Query timestamp is greater than all stored timestamps — Returns the value with the largest timestamp.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Leverage the problem constraint: 'Timestamps are strictly increasing on set calls.' Explain how this guarantees that appending to a dynamic array keeps it sorted without re-sorting.
  2. Show how binary search (upper_bound - 1) handles both exact matches and floor lookups in O(log N) time.
  3. Relate this to real-world architectures: append-only log databases, Git commit trees, and financial ledger time-travel queries.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What data structure should store the historical values for each key in TimeMap?

2.How does get(key, timestamp) find the value with the largest timestamp_prev <= timestamp in O(log N) time?

3.What is the time complexity of set() and get()?

Back to DSA Sheet