Time Based Key-Value Store - Video Solutions
Time Based Key-Value Store - Leetcode 981 - Python
Time Based Key-Value Store - Video Solution
Watch 10 video solutions for Time Based Key-Value Store, a medium level problem involving Hash Table, String, Binary Search. This walkthrough by NeetCode has 183,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 keykeywith the valuevalueat the given timetimestamp.String get(String key, int timestamp)Returns a value such thatsetwas called previously, withtimestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largesttimestamp_prev. If there are no values, it returns"".
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 foo at 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 <= 100keyandvalueconsist of lowercase English letters and digits.1 <= timestamp <= 107- All the timestamps
timestampofsetare strictly increasing. - At most
2 * 105calls will be made tosetandget.
Approach Overview
Problem Overview: Design a data structure that stores multiple values for the same key, each associated with a timestamp. When you call get(key, timestamp), return the value set for that key at the largest timestamp less than or equal to the given timestamp.
The main challenge is efficient historical lookup. Each key may have many timestamped values, and the query must quickly find the closest earlier timestamp. This naturally leads to combining a hash table for key lookup with binary search over timestamps.
Approach 1: HashMap with Sorted Timestamps (O(log n) get, O(1) set)
Store each key in a hash map where the value is a list of (timestamp, value) pairs. The problem guarantees timestamps are strictly increasing for each key, so every set operation simply appends to the list in O(1) time. For get, retrieve the list for the key and run binary search to find the largest timestamp less than or equal to the query timestamp. Many languages provide built-in helpers like bisect in Python. The binary search runs in O(log n) time where n is the number of values stored for that key, while the overall space complexity is O(n).
This approach works well because it leverages the monotonic timestamp guarantee. Since inserts always happen in increasing order, there is no need to re-sort or rebalance structures. You get constant-time writes and logarithmic-time historical reads.
Approach 2: HashMap with Manual Binary Search (O(log n) get, O(1) set)
The same core structure can be implemented manually when built-in binary search utilities are unavailable. Maintain a hash map from key to a vector or array of (timestamp, value) pairs. Each set appends the pair in O(1). During get, perform a classic binary search over the timestamp array: move the left or right pointer depending on whether the mid timestamp is greater or smaller than the query. Track the best candidate seen so far. The search takes O(log n) time and uses O(n) space for storage.
This version demonstrates deeper understanding of how design problems combine simple data structures with algorithmic primitives. Interviewers often expect you to write the binary search logic yourself in languages like C++ or Java.
Recommended for interviews: The HashMap + binary search design is the expected solution. A brute-force scan through all timestamps would take O(n) per query and does not scale. Showing the optimized approach proves you recognize sorted data patterns and can combine hashing with logarithmic search for efficient queries.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap with Sorted Timestamps (Built-in Binary Search) | set: O(1), get: O(log n) | O(n) | Best general solution when timestamps are inserted in increasing order and the language provides binary search helpers |
| HashMap with Manual Binary Search | set: O(1), get: O(log n) | O(n) | Preferred in interviews or languages where you implement binary search manually (C++, Java) |