LeetCode 981: Time Based Key Value Store — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Hash Table | Binary Search | Design | Data Structure

The Problem

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the value associated with a key at a given timestamp or the most recent timestamp before it.

Approach

Use a hash map where each key maps to a list of (timestamp, value) pairs sorted by timestamp. For retrieval, perform binary search to find the exact timestamp or the largest timestamp less than or equal to the target timestamp.

Time: O(log n) for get operations, O(1) for set operations · Space: O(n)

Code

class TimeMap:
    def __init__(self):
        self.data = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        values = self.data[key]
        left, right = 0, len(values) - 1

        while left <= right:
            mid = left + (right - left) // 2
            if values[mid][0] == timestamp:
                return values[mid][1]
            elif values[mid][0] < timestamp:
                left = mid + 1
            else:
                right = mid - 1

        if right >= 0:
            return values[right][1]
        return ""