981. Time Based Key-Value Store (Python)

Algorithms: Binary Search; Data Structure: Hash Maps, Heaps

Link to the problem: https://leetcode.com/problems/time-based-key-value-store/

Go ahead read the problem, try solving it and then come back for various approaches to the problem. This is a very good problem to get good understanding of binary search.

Problem explanation:

set(key, value, timestamp) function -> stores key, value, timestamp

get(key, timestamp) function -> returns the value corresponding to maximum stored timestamp that is less than given timestamp, else return “”. We need to find maximum stored timestamp corresponding to the given key.

Example:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Input: inputs=["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Approach 1:

set function: The brute force approach is to store inputs in a hashmap with KEY = key, VALUE = (timestamp, value).

get function:

1. Traverse through the VALUE correspond to given KEY. and find the index in the self.map[KEY] array whose timestamp is less than given timestamp.

2. Return value at that specific index if it’s greater than 0 else “”.

class TimeMap:
def __init__(self):
        self.dict = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
        index = -1
        for i in range(len(self.dict[key])):
            if values[i][0] <= timestamp              
                if index == -1:
                    index = i
                elif values[index][0] < values[i][0]: 
                        index = i
                
        return values[index][1] if index >= 0 else ""

Time Complexity: O(1) for set, O(N) for get where N could be total entries in worst case.

Space Complexity: O(N) to store all of the entries in dictionary.

Approach 2:

set function: Add all the (-timestamp, value) to the self.dict corresponding to the key. -timestamp is used to get timestamp out of the list in descending order from the heap.

get function:

1. Create a list of VALUE corresponding to the given key from dictionary. Heapify the list.
2. Pop out from heap (-timestamp, value) until the negative of popped out timestamp is greater than given timestamp. As soon as it’s less than given timestamp, return the value attached with timestamp in tuple.
3. Else return “” if nothing is returned and the heap is empty.

from heapq import *
class TimeMap:
def __init__(self):
        self.dict = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((-timestamp, value))
def get(self, key: str, timestamp: int) -> str:
        values = self.dict[key].copy()
        heapify(values)
        
        while values:
            t, v = heappop(values)
            if -t <= timestamp: 
                return v
        return ""

Time Complexity: O(1) for set, O(N*logN) for get where N could be total entries in worst case.

Space Complexity: O(N) to store all of the entries in dictionary.

Approach 3:

set function: The brute force approach is to store inputs in a hashmap with KEY = key, VALUE = (timestamp, value).

get function:

1. Set the l = 0, r = (length of list-1) where list is VALUE corresponding to the given key in dictionary.
2. Use the binary search approach and find the mid index whose timestamp at that index is equal to given timestamp. Return the value at that index.
3. If timestamp at mid index is less than given timestamp then move right by assigning l = mid+1, else assigning r = mid-1
4. If l > r at any point, return value at the index r. We need to return the value paired to the largest timestamp that is less than given timestamp. And we know that r < l, so r would give us the result.

class TimeMap:
def __init__(self):
        self.dict = defaultdict(list)
        
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
        l, r = 0, len(self.dict[key])-1
        
        while l <= r:
            mid = (l+r)//2
            if values[mid][0] == timestamp: return values[mid][1]
            elif values[mid][0] < timestamp:
                l = mid+1
            else:
                r = mid-1
                
        return values[r][1] if r >= 0 else ""

Time Complexity: O(1) for set, O(logN) for get where N could be total entries in worst case.

Space Complexity: O(N) to store all of the entries in dictionary.

Thank you for reading the blog. Like, share, subscribe if you liked my blog and i could help you in understanding the problem solution. Comment for any suggestions, query or feedback.

Happy blogging!