Problem Breakdown
We need to implement a TimeMap class that stores key-value pairs with associated timestamps. The core operations are:
- set(key, value, timestamp): Stores the entry. Timestamps for all set operations are strictly increasing globally.
- get(key, timestamp): Returns the latest stored value where its timestamp is less than or equal to the given
timestamp. If no such value exists (key missing or timestamps too new), return an empty string ("").
Key Constraints:
- Timestamps for all
setoperations are strictly increasing (). This guarantees that entries stored in a list per-key remain sorted by timestamp without explicit sorting. - Total number of calls (set + get) is up to 120,000. An linear scan for
getwould lead to Time Limit Exceeded (TLE), so we need logarithmic time complexity for retrieval.
Intuition
Since timestamps are strictly increasing globally across all operations, any list of entries associated with a specific key will naturally be sorted by timestamp in the order they were inserted into our data structure.
The problem reduces to finding the largest stored timestamp that is less than or equal to the query timestamp. In a sorted array (or list), this corresponds to an “upper bound” search where we want the rightmost element satisfying the condition target.
A naive linear scan for each get operation would take time, leading to quadratic behavior in worst-case scenarios with many queries on hot keys. By using Binary Search (specifically finding the upper bound), we can reduce this lookup to . We use a Hash Map (dict) where keys map to lists of [timestamp, value] tuples for efficient key access ().
Approach
- Initialization: Initialize an empty dictionary
self.store. This maps each stringkeyto a list containing pairs of[timestamp, value]. - set Operation:
- If the key does not exist in
store, create a new entry (list). - Append the current
[timestamp, value]pair to the existing list for that key. Because timestamps are strictly increasing globally, this maintains sorted order automatically without needing sort operations insideset.
- If the key does not exist in
- get Operation:
- Check if the key exists in
store. If not, return"". - Retrieve the list of entries for the key.
- Perform Binary Search to find the rightmost index where
entry[timestamp] <= query_timestamp.- Initialize pointers
left = 0,right = len(entries) - 1. - Maintain a variable (e.g.,
ans_idx) initialized to-1to track valid candidates. - While loop: Calculate
mid. Ifentries[mid][timestamp] <= query_timestamp, record index and move right (left = mid + 1). Else, move left (right = mid - 1).
- Initialize pointers
- Return the value at
ans_idxif found; otherwise return"".
- Check if the key exists in
Complexity Analysis
- Time Complexity:
set: amortized (hash map insertion and list append).get: where is the number of entries for that specific key. Since total operations are bounded, this ensures efficiency within limits ().
- Space Complexity:
- , where is the total number of elements stored across all keys (sum of lengths of lists in
self.store).
- , where is the total number of elements stored across all keys (sum of lengths of lists in
Solution
class TimeMap:
def __init__(self):
# Map key -> list of [timestamp, value]
self.store = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.store:
self.store[key] = []
# Append new entry. Timestamps are strictly increasing globally,
# so the list remains sorted by timestamp automatically.
self.store[key].append([timestamp, value])
def get(self, key: str, timestamp: int) -> str:
if key not in self.store or len(self.store[key]) == 0:
return ""
entries = self.store[key]
left, right = 0, len(entries) - 1
# Binary search to find the largest index where entry[timestamp] <= query_timestamp
ans_idx = -1
while left <= right:
mid = (left + right) // 2
if entries[mid][0] <= timestamp:
ans_idx = mid # Valid candidate found, try to go newer
left = mid + 1 # Move search space to the right
else:
right = mid - 1 # Current entry is too new
return "" if ans_idx == -1 else entries[ans_idx][1]
Edge Cases Handled
- Key Not Found: The
getmethod checks if the key exists inself.store. If missing, it immediately returns an empty string. - Timestamp Smaller than All Entries: Binary search logic sets
ans_idx = -1initially. If all stored timestamps are greater than the query timestamp (e.g., first entry is at , query is ), the conditionentries[mid][0] <= timestampwill never be met, leavingans_idxas-1. The method returns"". - Exact Timestamp Match: If a stored value exists exactly at the requested timestamp (e.g., entry
[5, "val"], query ), the condition holds. Binary search continues to try finding something newer (left = mid + 1). Since no later entries exist for that exact time or are older but valid, it returns the correct value associated withtimestamp. - Empty Store: If a key has been set once and then queried before any subsequent sets (or if store is empty), logic handles list length checks.