Time Based Key Value Store LeetCode Solution [Python]

Time Based Key Value Store LeetCode problem tasks you to create a data structure to store and retrieve key-value pairs with timestamps efficiently.

This problem falls under the category of designing a data structure to store key-value pairs with timestamps and efficiently retrieving values based on timestamps.

Problem Overview

So, the problem involves designing 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.

We are required to implement the TimeMap class, which includes two primary operations:

set(String key, String value, int timestamp): This operation stores the key key with the value value at the given timestamp timestamp.
get(String key, int timestamp): This operation returns a value such that the set operation was called previously with timestamp_prev <= timestamp. If there are multiple values, it should return the value associated with the largest timestamp_prev. If there are no values for the given key, it should return an empty string (“”).

Example 1:

Here’s an example to help you understand the problem better:

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"]

In this example, we create a TimeMap object, set values for the key “foo” at different timestamps, and then retrieve values for “foo” at specific timestamps.

Understanding the Constraints

Before we dive into the solution, let’s briefly discuss the constraints given in the problem:

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

Problem Solution

Now, let’s explore the efficient solution to this problem.

Efficient Approach to Time Based Key Value Store: Binary Search

To efficiently retrieve values based on timestamps, we can use a binary search approach.

The key insight is that the timestamps are strictly increasing, which means that when we store values, they are naturally sorted by timestamps.

We’ll implement the TimeMap class using a dictionary (hash map) where the keys are the keys of the data store, and the values are lists of pairs containing the value and timestamp. The timestamps in each list are sorted in increasing order.

Let’s take a look at the Python code for the efficient solution:

View on GitHub ➹

class TimeMap:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.keyStore = {}  # key: list of [value, timestamp]

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = []
        self.keyStore[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        res, values = "", self.keyStore.get(key, [])
        l, r = 0, len(values) - 1
        while l &lt;&equals; r:
            m = (l + r) // 2
            if values[m][1] &lt;&equals; timestamp:
                res = values[m][0]
                l = m + 1
            else:
                r = m - 1
        return res

Time and Space Complexity

Time Complexity:
- The set operation has a constant time complexity of O(1) because we are using a dictionary to store the data.
- The get operation has a time complexity of O(log n), where n is the number of values associated with the key. This is due to the binary search.
Space Complexity:
- The space complexity is O(n), where n is the total number of values stored in the data structure. This accounts for the space used to store key-value pairs.

Reasoning Behind Our Approach

The efficient approach takes advantage of the sorted timestamps to achieve O(log n) time complexity for the get operation.

We use a binary search to find the value associated with the specified timestamp. The binary search is efficient because the timestamps are sorted in increasing order.

Our data structure stores values for each key in a dictionary, making the set operation straightforward and efficient with O(1) complexity.

Solve These LeetCode Next

Conclusion

In this blog post, we tackled the LeetCode problem “Time Based Key Value Store” and provided an efficient Python solution using binary search.

We designed the TimeMap class to store key-value pairs with timestamps and retrieve values based on timestamps.

The binary search approach allows us to efficiently find the closest value to a given timestamp.

If you’d like to explore the code further or test it with additional cases, you can find it on LeetCode here.

Feel free to comment, ask questions, make suggestions, or share this content with others. Happy coding!