Time Based Key‑Value Store in TypeScript: Find the Latest Eligible Version

Asking for a value "at time ten" doesn't necessarily mean a write happened at time ten. Often it means finding the latest value that was already in effect. That distinction is the whole point of LeetCode's Time Based Key‑Value Store problem.
For each key, we keep a history of timestamped values. A read returns the value associated with the greatest stored timestamp no later than the requested time. If there isn't one, it returns an empty string. The history can have gaps; we don't fill every missing timestamp with another copy of the previous value.
The helpful constraint is that write timestamps are strictly increasing. We can append records in order and search them without sorting. I'll use an upper‑bound search: find the first record that is too new, then step back once.
Store the History That the Query Needs
A map separates the histories by key. Each history is an array of records containing a timestamp and value. There is no need for one global array, because a query asks about one key and should not scan unrelated writes.
Keeping each timestamp beside its value avoids parallel arrays whose positions must remain synchronised. A record also makes the search comparison explicit: we compare its timestamp and return its value. The two fields have different jobs even though they travel together.
A write creates the key's array if necessary, then appends a record. It doesn't overwrite the previous value, because that older value may still answer a historical query. The data structure's memory therefore grows with the number of writes, not merely the number of distinct keys.
The problem's global timestamp ordering implies ordering within every individual key's history. That implication matters: our array can remain sparse in time and still be sorted. We don't need neighbouring records to have consecutive timestamps.
type Version = { timestamp: number; value: string };
class TimeMap {
private readonly history = new Map<string, Version[]>();
set = (key: string, value: string, timestamp: number): void => {
let versions = this.history.get(key);
if (!versions) {
versions = [];
this.history.set(key, versions);
}
versions.push({ timestamp, value });
};
get = (key: string, timestamp: number): string => {
const versions = this.history.get(key);
if (!versions) return '';
let low = 0;
let high = versions.length;
while (low < high) {
const middle = low + Math.floor((high - low) / 2);
if (versions[middle].timestamp <= timestamp) low = middle + 1;
else high = middle;
}
return low === 0 ? '' : versions[low - 1].value;
};
}These method signatures match the exercise. There is no runtime check for increasing timestamps because the input contract supplies that guarantee. If this became a reusable application class, I would either enforce the ordering or document it prominently at the write boundary. A type annotation on number cannot establish temporal order.
Why Search for the First Record That is Too New?
Suppose a key has records at times 3, 8, and 14. A read at time ten should use the record at eight. Testing whether each timestamp is greater than ten produces false, false, true. We want the first true position, which is index two, then return the preceding record at index one.
The code expresses the same decision from the other side: timestamps at or before the query are eligible, so it moves low past them. A timestamp after the query moves high back to its index. Equality belongs to the eligible side, because a value written at the requested time is already available.
The unresolved interval is [low, high). Positions before low have been established as eligible. Positions at or after high have been established as too new, when those positions exist. At termination the endpoints meet at the dividing position.
That position can be zero, meaning every record is too new. It can equal the history length, meaning every record is eligible. Treating those positions as useful answers rather than exceptional accidents makes the outer cases straightforward.
Follow Reads Around the Gaps
Imagine the key theme receives light at time three, dark at time eight, and contrast at time fourteen. Reading at time two returns an empty string, because no stored value existed early enough. The upper bound is zero, so there is no preceding record to read.
Reading at three returns light. Reading at seven also returns light; the gap doesn't erase the value. Reading at eight returns dark, and reading at thirteen still returns dark. Reading at fourteen or later returns contrast.
An unknown key returns immediately before any binary search. It must not create an empty history as a side effect of reading. Queries are observations, and changing the set of stored keys during a failed lookup would add unnecessary state to maintain.
Now interleave writes to another key. Its records go into a different array and cannot change these answers. This sounds obvious, but an implementation that binary‑searches a global list and then checks the key can easily skip an older matching record behind newer unrelated writes.
The Loop's Equality Choice is the Feature
My first and last position article uses the same upper‑bound idea to find the end of a duplicate run. Here, the search ends a run of eligible timestamps. The array values need not equal the query; the comparison decides which side of a time boundary they occupy.
Returning immediately on an exact match could work with the strict timestamp uniqueness provided here, but it would complicate the explanation and leave the gap case to another path. One search that always finds the first ineligible position handles exact hits and gaps consistently.
I also avoid searching for the query plus one. Comparing timestamps directly with <= expresses the intended relation without relying on a successor value or extra arithmetic near a numeric limit. Within the exercise's bounds both are possible, but the direct comparison is easier to preserve when the representation changes.
Each iteration reduces the number of unresolved positions. A failed eligibility test keeps the midpoint as the excluded high endpoint, and a successful test advances beyond it. The loop cannot remain on the same two positions indefinitely, a detail worth checking before trusting any compact binary search.
What the Costs Depend on
If a particular key has m versions, its read takes O(log m) comparisons after the map lookup. Appending a version is amortised O(1) under the usual dynamic‑array and average constant‑time hash‑map model. Total storage is O(w) records for w writes, plus the stored key and value text.
Those bounds treat comparing numeric timestamps as constant work and don't pretend string payloads occupy no memory. If values are large documents, their sizes dominate storage even though the number of records remains unchanged. The ECMAScript Map specification requires sublinear average access rather than mandating an exact hash‑table implementation.
There is no retention policy, persistence layer, concurrency control, or transaction model here. An application that keeps every historical value indefinitely would need to decide when old versions can be discarded and what a query before the retained history means. Returning an empty string may be sufficient for the exercise but too ambiguous for a real interface that also allows empty stored values.
Ordering Changes the Design
If writes arrive out of order, appending breaks the search precondition. Sorting on every read would restore order at an avoidable cost, and inserting into a sorted array can require shifting O(m) records. A tree or a separate ingestion‑and‑compaction policy might be more appropriate, depending on write volume and latency requirements.
The important point is to revisit the data structure when the ordering promise changes. Binary search doesn't make an unsorted history mostly correct; it makes its incorrect answers look impressively efficient.
I verify this version against a reference that scans a key's records and selects the greatest eligible timestamp. Tests cover unknown keys, reads before the first write, exact timestamps, gaps, reads after the final write, and heavily interleaved keys. My binary search foundations article explains the shrinking interval; this example shows why the question being searched matters just as much as the loop.