LeetCode Solutions Blog

Time Based Key-Value Store

Number: 1023

Difficulty: Medium

Paid? No

Problem Description

Design 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. The data structure should support set(key, value, timestamp) to store a value and get(key, timestamp) to retrieve the value corresponding to the highest timestamp less than or equal to the query timestamp.

Key Insights

Use a dictionary (hash table) to map each key to a list of (timestamp, value) pairs.
Timestamps are strictly increasing when setting the values, which allows efficient appending.
For getting the value, perform a binary search on the list of timestamps to find the largest timestamp that is <= the queried timestamp.
If no valid timestamp exists, return an empty string.

Space and Time Complexity

Time Complexity:

set operation: O(1) per call (amortized).
get operation: O(log N) per call, where N is the number of timestamps stored for the key. Space Complexity: O(total number of set calls), to store all (timestamp, value) pairs.

Solution

We use a hash table to store keys mapping to a list of their timestamps and corresponding values. Since the timestamps are inserted in strictly increasing order, the list remains sorted. For the get operation, a binary search is applied to quickly locate the appropriate value for a given timestamp. This approach minimizes the lookup time and efficiently handles the problem constraints.

Code Solutions

# TimeMap class in Python with line-by-line comments.
class TimeMap:
    def __init__(self):
        # Initialize the dictionary to hold key and list of (timestamp, value) pairs.
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Append the new (timestamp, value) pair for the given key.
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # Return the value for the largest timestamp <= the given timestamp.
        if key not in self.store:
            return ""
        
        values = self.store[key]
        left, right = 0, len(values) - 1
        
        # Binary search for the rightmost index with timestamp <= given timestamp.
        while left <= right:
            mid = (left + right) // 2
            if values[mid][0] <= timestamp:
                left = mid + 1
            else:
                right = mid - 1
        
        # If no valid timestamp exists, right will be -1.
        if right == -1:
            return ""
        return values[right][1]

# Example usage:
# timeMap = TimeMap()
# timeMap.set("foo", "bar", 1)
# print(timeMap.get("foo", 1))  # Output: "bar"
# print(timeMap.get("foo", 3))  # Output: "bar"
# timeMap.set("foo", "bar2", 4)
# print(timeMap.get("foo", 4))  # Output: "bar2"
# print(timeMap.get("foo", 5))  # Output: "bar2"