Time Based Key-Value Store
Last Updated: March 29, 2026
Understanding the Problem
We need to build a data structure that associates keys with values, but with a twist: each key can have multiple values stored at different points in time. When we retrieve a value, we don't just want the latest one. We want the value that was current at a specific timestamp, meaning the value set at the largest timestamp that doesn't exceed our query timestamp.
Think of it like version control for a key-value store. Each set call creates a new version, and each get call asks "what was the value at this point in time?" If no exact match exists, we want the most recent version before that time.
The critical observation is that timestamps for set calls are strictly increasing. This means the timestamps for each key are already sorted, which opens the door to binary search instead of scanning through every entry.
Key Constraints:
1 <= timestamp <= 10^7and timestamps are strictly increasing -- The sorted order of timestamps is guaranteed. We never need to sort anything ourselves.- At most
2 * 10^5calls tosetandget-- With up to 200,000 operations, a linear scan pergetcall could mean up to 200,000 200,000 = 4 10^10 operations in the worst case. We need something better forget. key.length, value.length <= 100-- String operations are cheap. The bottleneck is the lookup strategy, not string handling.
Approach 1: Hash Map with Linear Scan
Intuition
The most straightforward design stores each key's history as a list of (timestamp, value) pairs inside a hash map. For set, we just append to the list. For get, we scan backward through the list to find the largest timestamp that doesn't exceed the query timestamp.
Since timestamps come in strictly increasing order, the list is naturally sorted. Scanning backward means we hit the most recent valid entry first, so we can return as soon as we find a timestamp less than or equal to our target.
Algorithm
- Initialize a hash map where each key maps to a list of (timestamp, value) pairs.
- For
set(key, value, timestamp): append(timestamp, value)to the list forkey. - For
get(key, timestamp): look up the list forkey. Iterate backward through the list. Return the value of the first entry whose timestamp is less than or equal totimestamp. If no such entry exists, return"".
Example Walkthrough
Code
- Time Complexity: O(1) for
set, O(n) forgetwhere n is the number of entries for that key.setappends to a list in O(1) amortized.getmay scan all entries in the worst case. - Space Complexity: O(m) where m is the total number of
setcalls. We store every (timestamp, value) pair.
The linear scan works but doesn't leverage the sorted order of timestamps. Since timestamps are strictly increasing, can we use binary search to find the right entry in O(log n) instead of O(n)?
Approach 2: Hash Map with Binary Search (Optimal)
Intuition
Since timestamps arrive in strictly increasing order, the list of timestamps for each key is already sorted. This is exactly the setup where binary search shines. Instead of scanning backward through potentially thousands of entries, we can jump straight to the right answer in O(log n) time.
The specific binary search variant we need is "find the largest value less than or equal to the target." This is sometimes called finding the "floor" value. We want the rightmost timestamp that doesn't exceed our query timestamp.
Here's how the binary search works: we maintain a search range [left, right]. We check the middle element. If timestamps[mid] <= target, this could be our answer, but there might be a better (larger) one to the right, so we move left = mid + 1 and record mid as a candidate. If timestamps[mid] > target, the middle timestamp is too new, so we move right = mid - 1. When the search ends, our last recorded candidate is the answer.
The binary search exploits the sorted order of timestamps. At each step, we cut the search space in half. When we find a timestamp that's valid (less than or equal to the target), we don't stop. We record it as a candidate and keep searching to the right for a potentially larger valid timestamp. When we find a timestamp that's too large, we search to the left. By the end, result holds the index of the largest valid timestamp, or -1 if none exists.
This is a standard "find the floor" binary search pattern. It comes up frequently in problems involving sorted data where you need the closest element that doesn't exceed a threshold.
Algorithm
- Initialize a hash map where each key maps to a list of (timestamp, value) pairs.
- For
set(key, value, timestamp): append(timestamp, value)to the list forkey. - For
get(key, timestamp): - Look up the list for
key. If the key doesn't exist, return"". - Binary search the timestamps for the largest one less than or equal to
timestamp. - Set
left = 0,right = list.size() - 1,result = -1. - While
left <= right: computemid = (left + right) / 2. Iftimestamps[mid] <= timestamp, setresult = midand moveleft = mid + 1. Otherwise, moveright = mid - 1. - If
result != -1, return the value at indexresult. Otherwise, return"".
Example Walkthrough
Code
- Time Complexity: O(1) for
set, O(log n) forgetwhere n is the number of entries for that key.setappends to a list and does a hash map lookup, both O(1) amortized.getperforms a hash map lookup in O(1) and then binary search over at most n timestamps in O(log n). - Space Complexity: O(m) where m is the total number of
setcalls. We store every timestamp-value pair.