Time-versioned map

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A key called foo was set to bar at time 1, to bar2 at time 4, and to bar3 at time 7. Someone asks: what was foo at time 3? You look at the history and answer bar, because at time 3 the latest change so far was the one at time 1. At time 5 the answer is bar2. At time 7 it is bar3.

A plain dictionary cannot answer this; it holds one value per key and forgets the past. Keeping a list of (time, value) pairs per key and scanning it from the end works, but with a million writes to one key each read scans up to a million pairs.

Build the structure, one piece at a time

Piece one is a dictionary from key to a list. Piece two is what goes in the list: pairs (timestamp, value), appended in the order they arrive. The problem promises that timestamps only increase, so appending keeps each list sorted by time with no extra work:

Piece three is how to read. A question "value at time t" means "the pair with the largest timestamp that is at most t". Because the list is sorted, binary search finds it: keep a range of candidates, look at the middle pair, and if its timestamp is at most t it is a candidate and everything to its right might be better, so move the left edge past it; otherwise move the right edge before it. For get(foo, 5): the middle pair is (4, bar2), 4 ≤ 5, so remember bar2 and look right; the only pair there is (7, bar3), 7 > 5, discard it; the answer is bar2. For get(foo, 3): middle (4, bar2) has 4 > 3, look left; (1, bar) has 1 ≤ 3, answer bar. A time before the first write has no answer and returns the empty string.

Why it is correct

The invariant is that each key's list is sorted by timestamp and contains every write to that key. Sorted order is guaranteed because writes arrive with increasing timestamps and are appended at the end; if a problem did not promise that, you would insert at the sorted position instead, and the rest is unchanged.

The binary search is a search for a boundary. Define a pair as "good" when its timestamp is at most t. In a sorted list the good pairs form a prefix: all good, then all bad. The wanted pair is the last good one. Each step of the search keeps the last good pair inside the range or already remembered, and halves the range, so when the range is empty the remembered pair is the rightmost good one, which is the latest value at or before t.

Why it is fast

set is one dictionary lookup plus one append: O(1). get is one dictionary lookup plus a binary search over the key's list of n writes. The search halves the range each step, so it takes ⌈log₂ n⌉ + 1 steps, which is 21 steps for a million writes, against a million for the scan:

steps = ⌈log₂ n⌉ + 1

The memory is one pair per write, which is the minimum for a structure that must answer about any past time.

How to recognise it in an interview

Cues: "at timestamp", "return the value as it was at time t", "snapshot", "the latest price before", "version". Any time a structure must remember history and be queried about a past moment, think of a sorted list per key with binary search. Say: "I will store (timestamp, value) per key in arrival order and binary search for the last timestamp at or before t".

Time Based Key-Value Store is the structure above. Snapshot Array is the same thing with one list per array index and the snapshot number as the timestamp, so a value is stored only when it changes, not on every snapshot. Stock Price Fluctuation keeps the latest price per timestamp in a map and adds two heaps for the current maximum and minimum, since prices there can be corrected after the fact.

02The idea in one line

Store (timestamp, value) lists per key; binary search the latest ≤ t.

Reach for it when: Time based key-value store, snapshot array, stock price with timestamps.

Cost: O(log n) per get.

03The walk-through, step by step

The video works one example: TimeMap set foo@1=bar, set foo@4=bar2, get foo@3. These are its captions in order, so you can follow without the video or check a step you missed.

1. Each key owns a list of (timestamp, value), sorted by timestamp
2. set(foo, bar, 1): append to the end
3. set(foo, bar2, 4): append to the end
4. set(foo, bar3, 7): append to the end
5. get(foo, 3): binary search the last timestamp ≤ 3
6. timestamp 1 ≤ 3: answer bar
7. get(foo, 7): binary search the last timestamp ≤ 7
8. timestamp 7 ≤ 7: answer bar3
9. get(foo, 5): binary search the last timestamp ≤ 5
10. timestamp 4 ≤ 5: answer bar2
11. set is O(1) append; get is O(log n) per key

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Design: Hash map + doubly linked list (LRU), Hash map + array for O(1) random, Lazy iterators, Ordered intervals (range module), Streaming data structures.