# Time Based Key-Value Store

- **Canonical ID**: `time-based-key-value-store`
- **Canonical URL**: https://dsacheatsheet.com/problems/time-based-key-value-store
- **Difficulty**: medium
- **Patterns**: Binary Search, Arrays & Hashing
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/time-based-key-value-store/

## 1. Core Invariant / The Trick

Since `set()` timestamps are strictly increasing per key, appending `(timestamp, value)` keeps the per-key list sorted automatically in O(1). `get()` binary searches the rightmost `t <= timestamp`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log N)`
- **Space Complexity**: `O(N)`
- **Proof**: Monotonic timestamp constraint removes sorting overhead on writes; reads perform standard upper-bound minus 1 binary search.

## 3. Minimal Idiomatic Code

### Python
```python
class TimeMap:
    def __init__(self):
        self.store = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        arr = self.store.get(key)
        if not arr: return ""
        l, r, ans = 0, len(arr) - 1, ""
        while l <= r:
            m = (l + r) // 2
            if arr[m][0] <= timestamp:
                ans = arr[m][1]
                l = m + 1
            else:
                r = m - 1
        return ans
```

### TypeScript
```typescript
export class TimeMap {
  private store = new Map<string, Array<[number, string]>>();
  set(key: string, value: string, timestamp: number): void {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key)!.push([timestamp, value]);
  }
  get(key: string, timestamp: number): string {
    const arr = this.store.get(key);
    if (!arr) return '';
    let l = 0, r = arr.length - 1, ans = '';
    while (l <= r) {
      const m = (l + r) >> 1;
      if (arr[m][0] <= timestamp) { ans = arr[m][1]; l = m + 1; } else { r = m - 1; }
    }
    return ans;
  }
}
```

### C++
```cpp
class TimeMap {
    unordered_map<string, vector<pair<int, string>>> m;
public:
    void set(string k, string v, int t) { m[k].push_back({t, v}); }
    string get(string k, int t) {
        auto& arr = m[k]; int l = 0, r = (int)arr.size() - 1; string ans;
        while (l <= r) { int mid = (l + r) / 2; if (arr[mid].first <= t) { ans = arr[mid].second; l = mid + 1; } else r = mid - 1; }
        return ans;
    }
};
```

### Java
```java
class TimeMap {
    Map<String, List<Map.Entry<Integer, String>>> m = new HashMap<>();
    public void set(String k, String v, int t) { m.computeIfAbsent(k, x -> new ArrayList<>()).add(Map.entry(t, v)); }
    public String get(String k, int t) {
        var arr = m.getOrDefault(k, List.of()); int l = 0, r = arr.size() - 1; String ans = "";
        while (l <= r) { int mid = (l + r) >>> 1; if (arr.get(mid).getKey() <= t) { ans = arr.get(mid).getValue(); l = mid + 1; } else r = mid - 1; }
        return ans;
    }
}
```

### Go
```go
type TimeMap struct { m map[string][]struct{ t int; v string } }
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Returning `""` (empty string) when key is absent or all timestamps exceed target.

### Follow-ups
- Snapshot Array applies this same versioned timestamp pattern per index.