← DSA Atlas
Dedicated problem page · #981

Time Based Key-Value Store

MediumBinary SearchTimestamped history with binary searchBinary search over an append-only sorted list (data structure design)
Solve on LeetCode ↗
981
MediumBinary SearchBinary search over an append-only sorted list (data structure design)Timestamped history with binary search

Time Based Key-Value Store

Design a time-based key-value store supporting two operations. set(key, value, timestamp) stores the key with the given value at time timestamp. get(key, timestamp) returns the value that was set for key at the largest stored time_prev <= timestamp; if no such value exists, return the empty string "". For each key, set is called with strictly increasing timestamps.

Open official problem prompt ↗
In plain English

Answer 'what was this key's value as of time T?' quickly, given writes that arrive in time order.

Picture it like this

Like reading a document's edit history: to see the text as it stood on a certain date, you jump to the latest revision made on or before that date rather than replaying every edit.

Example
Input
set("foo","bar",1); get("foo",1); get("foo",3)
Output
"bar", "bar"
Why
get(foo,1) matches the value stored exactly at time 1; get(foo,3) finds no later entry, so it falls back to the value at time 1, still "bar".
Constraints
1 <= key.length, value.length <= 100key and value consist of lowercase English letters and digits1 <= timestamp <= 10^7All set timestamps for a given key are strictly increasingAt most 2*10^5 calls total to set and get
Pattern lesson

See the pattern, then code

Timestamped history with binary search
Recognition clue

You must retrieve the most recent value not exceeding a query time, and inserts arrive in increasing time order - a sorted per-key history begging for binary search on get.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. Because timestamps for a key only increase, each key's list of (time, value) pairs is already sorted by time. A get is then a search for the rightmost entry whose time is <= the query, which binary search finds in logarithmic time.

New words, made simpleKnow these before the algorithm
Append-only log
A list you only add to, never reorder; here each key's history grows at the end.
Floor query
Finding the largest stored key not greater than the target - the search get performs on timestamps.
Rightmost <= target
The binary-search variant that keeps moving right while entries qualify, remembering the last valid one.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan of history

Simple but too slow when a key accumulates many versions and gets are frequent.

On get, walk the key's list backward to the first timestamp <= query.

Time O(n) per getSpace O(n)
Best choiceSorted list + binary search

Fast gets with trivial O(1) appends, matching the input's increasing-timestamp guarantee.

Exploit that appends are time-ordered, then binary search for the floor timestamp on get.

Time O(log n) per getSpace O(n)
The rule we keep true

Invariant

For every key, its stored list of (timestamp, value) pairs is sorted in increasing timestamp order at all times.

Why this is correct

Reasoning

The problem guarantees set is called with strictly increasing timestamps per key, so appending keeps each list sorted without any extra work. A sorted list makes get a floor query: binary search advances lo past every entry with time <= query, caching that entry's value, and rejects the rest. The last cached value is exactly the newest entry not exceeding the query time; if none qualifies the cached value stays the empty string.

The algorithm in three movesSay these aloud before coding
1Keep a dict mapping each key to a list of (timestamp, value) pairs

store = {'foo': [(1,'bar')]}

2On set, append the pair - the list stays sorted because times increase

get('foo',1): mid=0 ts=1<=1 -> res='bar'

3On get, binary search that list for the largest timestamp <= the query

get('foo',3): mid=0 ts=1<=3 -> res='bar'

4Track the best candidate value while narrowing the window

5Return the tracked value, or "" if nothing qualifies

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
(1,bar)0
get t=11
get t=32
1 · Readset(foo,bar,1)
2 · AskWhere does the pair go?
3 · Update statestore={'foo':[(1,'bar')]}
4 · ResultAppended at the end; list still sorted
Key takeaway

A single key foo whose history holds one timestamped value that answers both queries.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-3Per-key history map

    Each key maps to its own chronologically ordered list of value versions.

  2. 2
    Lines 5-6Constant-time set

    setdefault creates the list on first use; append keeps ordering for free because times increase.

  3. 3
    Lines 8-11Set up the floor search

    res defaults to "" so an absent key or a query before the first write returns the empty string.

  4. 4
    Lines 12-19Rightmost-<= binary search

    When arr[mid] qualifies, record it and search right for something newer; otherwise cut the right half.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • get for a key that was never set (return "")
  • get with a timestamp earlier than the key's first set (return "")
  • get with a timestamp far beyond the last set (return the last value)
  • Multiple sets then a get landing exactly on a stored timestamp
!

Common beginner mistakes

  • Returning the wrong bound: you want the largest time <= query, not the smallest time >= query
  • Forgetting to cache res before moving lo, losing the candidate
  • Assuming timestamps could arrive out of order and sorting unnecessarily on every set
  • Returning None or raising instead of the required empty string for a miss
Check your understanding

Why is no sorting needed inside set despite get relying on a sorted list?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search