Skip to main content
Talentd

Time Based Key-Value Store - Solution & Explanation

MediumHash TableStringBinary SearchDesign12 min readAsked at: Amazon, Microsoft, Apple +31
Practice this problem

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:

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 <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 107
  • All the timestamps timestamp of set are strictly increasing.
  • At most 2 * 105 calls will be made to set and get.

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.

Approach 1: HashMap with Sorted Timestamps

This approach uses a HashMap where each key points to a sorted list of timestamp-value pairs. The 'set' function appends the value along with the timestamp to the list associated with the key. The 'get' function retrieves the value at a particular timestamp by performing a binary search to find the rightmost timestamp less than or equal to the requested timestamp.

In the Python solution, we employ the 'bisect_right' function from the 'bisect' module to perform a binary search. The key-value pairs are stored such that each key corresponds to a list of (timestamp, value) tuples. The 'set' method stores the new data point in logarithmic time complexity due to the sorted insertion. The 'get' method uses binary search to efficiently find the largest timestamp less than or equal to the given timestamp.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.

Try this approach in the editor →

Approach 2: HashMap with Manual Binary Search

This approach is similar, but instead of using a helper library for the binary search, we implement it manually. This approach provides more control over the binary search process.

In C++, we use an unordered_map to keep track of all the keys. Every key maps to a vector of pairs, where each pair is a timestamp and its corresponding value. By manually coding the binary search, we find the accurate position to get the right timestamp in logarithmic time complexity.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.

Try this approach in the editor →

Approach 3: Hash Table + Ordered Set (or Binary Search)

We can use a hash table kvt to record key-value pairs, where the key is the string key and the value is an ordered set. Each element in the set is a tuple (timestamp, value), representing the value value corresponding to the key key at the timestamp timestamp.

When we need to query the value corresponding to the key key at the timestamp timestamp, we can use the ordered set to find the largest timestamp timestamp' such that timestamp' leq timestamp, and then return the corresponding value.

In terms of time complexity, for the set operation, since the insertion operation of the hash table has a time complexity of O(1), the time complexity is O(1). For the get operation, since the lookup operation of the hash table has a time complexity of O(1) and the lookup operation of the ordered set has a time complexity of O(log n), the time complexity is O(log n). The space complexity is O(n), where n is the number of set operations.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
HashMap with Sorted Timestamps

Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.

HashMap with Manual Binary Search

Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.

Hash Table + Ordered Set (or Binary Search)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 Searchset: O(1), get: O(log n)O(n)Preferred in interviews or languages where you implement binary search manually (C++, Java)

Video Solution

Time Based Key-Value Store - Leetcode 981 - Python • NeetCode • 183,293 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Time Based Key-Value Store easy or hard?
Time Based Key-Value Store is rated Medium difficulty on LeetCode. The implementation is straightforward once you recognize that timestamps are sorted, but identifying the need for binary search and designing the data structure correctly is the key challenge.
Time Based Key-Value Store Python/Java solution
Python solutions typically store lists of (timestamp, value) pairs and use the bisect module for binary search. Java implementations store pairs in an ArrayList and implement binary search manually to find the closest valid timestamp.
How to solve Time Based Key-Value Store in O(log n)?
Store each key in a hash map with a sorted list of timestamps and their values. When retrieving a value, run binary search to find the largest timestamp less than or equal to the requested timestamp. This reduces lookup from linear scanning to O(log n).
What is the best approach for Time Based Key-Value Store?
The optimal approach uses a HashMap that maps each key to a list of (timestamp, value) pairs stored in increasing timestamp order. Each set operation appends in O(1) time, and get operations use binary search to find the closest timestamp less than or equal to the query. This results in O(log n) lookup time and O(n) total space.
Is Time Based Key-Value Store asked at Google/Amazon/Meta?
Design problems combining hash maps and binary search frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of time-based storage systems and versioned key-value lookups test both data structure design and search optimization skills.
What data structure is used in Time Based Key-Value Store?
The solution primarily uses a hash table to map each key to its history of values. Each key stores an array or list of timestamp-value pairs, and binary search is used on this sorted list to efficiently locate the correct value.
What is the time complexity of Time Based Key-Value Store?
The set operation runs in O(1) because new values are appended to the timestamp list. The get operation performs binary search over the timestamps for that key, which takes O(log n) time. Space complexity is O(n) for storing all key-value timestamp entries.

Ready to solve this problem?

Practice Time Based Key-Value Store with our built-in code editor and test cases.

Practice on FleetCode
Previous

Stock Price Fluctuation