loading

Time Based Key-Value Store — Step-by-Step Visualization

mediumLeetCode #981Hash TableStringBinary SearchDesign

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps. Implement `set(key, value, timestamp)` and `get(key, timestamp)` — `get` returns the value with the largest timestamp ≤ the given timestamp, or `""` if none exists.

Algorithm Pattern

Hash Map + Binary Search

Key Idea

Store values as a list of [value, timestamp] pairs per key (timestamps always arrive in order). Use binary search on the timestamp list to find the largest timestamp ≤ the query.

Step-by-Step Approach

  1. set: append [value, timestamp] to store[key].
  2. get: binary search in store[key] for largest timestamp ≤ query.
  3. lo=0, hi=len-1. If vals[mid][1] <= timestamp: res=vals[mid][0], lo=mid+1.
  4. Else: hi=mid-1.
  5. Return res (empty string if never found).

Common Gotchas

  • Timestamps in set() always increase — binary search is valid.
  • get() returns the value at the latest timestamp that is still ≤ query.

Related Problems

← All problems