View Time Based Key-Value Store on LeetCode
Statistics
Time Complexity
O(log n) - Initializing and setting a value takes O(1) time, but the get method takes O(log n) because we are performing a binary search on a sorted list.
Space Complexity
O(n) - We must store all the input data given on a set method call, resulting in the O(n) space complexity.
Runtime Beats
72.53% of other submissions
Memory Beats
59.42% of other sumbissions
Explanation
TimeMap When the TimeMap class is initialized, we create the dictionary dic.
Set When the set method is called, we check if the key has been stored before; if not, we must initialize the dictionary as an empty list.
For all set calls, we will then append a tuple of both the value and its timestamp to the input key’s list.
Get When the get method is called, we create temporary variables: values to store all the values at the input key, l and r which are the binary search pointers, and closest_val that stores the closest value that is less than the input timestamp.
Begin the while loop until l is greater than r.
We create and initialize the mid variable and extract the value and time at that index from the values list.
If the current time is less than the input timestamp, it may be the closest value to the input timestamp, so we increment the left pointer and re-assign the closest_val.
If the time is greater than the timestamp, then we re-assign the right pointer and do not update closest_val.
Once the binary search while loop exits, the closest value to the input timestamp will be returned, and if no values are found, the default closest_val will be returned.
Data Structure and Algorithm Used
Hash Map (Dictionary) - A data structure that maps keys to their values. Each key may only appear once.
Binary Search - A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.
Visual Examples
Illustration of key value pair mapping, click to view
Binary search being performed on an array that contains the target, click to view
Binary search being performed on an array that does not contain the target, click to view
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class TimeMap:
def __init__(self):
self.dic = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.dic:
self.dic[key] = []
self.dic[key].append((value,timestamp))
def get(self, key: str, timestamp: int) -> str:
values = self.dic.get(key,[])
l,r = 0, len(values)-1
closest_val = ""
while l <= r:
mid = (l+r)//2
val,time = values[mid]
if time <= timestamp:
l = mid + 1
closest_val = val
else:
r = mid - 1
return closest_val