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

**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

```python
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 ""
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0981_time-based-key-value-store)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0981_time-based-key-value-store) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*