Time Based Key-Value Store

mediumTests passed 2026-11-11v1.0.0
TC: O(log N)|SC: O(N)
Binary SearchArrays & HashingOriginal Statement (leetcode).md

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

Monotonic timestamp constraint removes sorting overhead on writes; reads perform standard upper-bound minus 1 binary search.

3. Minimal Idiomatic Code

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

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Binary Search (O(log N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.