Leetcode:981. time based key value storage [trap of iteration for: on]

analysis

Simple dict + Two points
however, Pay attention to two dict

Timeout trap ： Extract sub elements on

class TimeMap:

    def __init__(self):
        self.d = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d[key].append((timestamp, value))


    def get(self, key: str, timestamp: int) -> str:
        if key not in self.d:
            return ""
        if timestamp < self.d[key][0][0]:
            return ""
        lst = [item[0] for item in self.d[key]]
        idx = bisect_right(lst, timestamp)
        if idx == 0:
            return ""
        else:
            return self.d[key][idx - 1][1]



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

ac code： Separate records

class TimeMap:

    def __init__(self):
        self.d1 = defaultdict(list)
        self.d2 = defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.d1[key].append(value)
        self.d2[key].append(timestamp)


    def get(self, key: str, timestamp: int) -> str:
    
        
        idx = bisect_right(self.d2[key], timestamp)
        if idx == 0:
            return ""
        else:
            return self.d1[key][idx - 1]



# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

summary

Pay attention to hidden on Time complexity