Leetcode 981. Time Based Key-Value Store

Let's understand what we're being asked to design. We need a time-based key-value store that can store multiple values for the same key, each with a different timestamp.

For example, if we do set('foo', 'bar', 1) and later set('foo', 'baz', 3), the key 'foo' now has two values: 'bar' at timestamp 1 and 'baz' at timestamp 3.

When we call get('foo', 2), we need to return the value whose timestamp is the largest timestamp less than or equal to 2. In this case, that's 'bar' (timestamp 1), because timestamp 3 is too large.

Important constraint: Timestamps for each key are strictly increasing - we never set the same key with an earlier timestamp than a previous set. This means for each key, the timestamps are naturally sorted!

Edge cases to consider: What if we get() a key that doesn't exist? What if we get() with a timestamp smaller than all stored timestamps for that key? What if we have up to 2e5 operations - how do we keep get() efficient?

Store a hash map where each key maps to a list of (timestamp, value) pairs. For set(), append the new pair to the key's list. For get(), iterate through the entire list for that key, checking each timestamp to find the largest one that is ≤ the query timestamp. This approach is simple to implement but requires scanning all timestamps for each get() operation, making it inefficient when a key has many historical values.

For each key, we're storing a list of (timestamp, value) pairs that grows over time. Because timestamps are strictly increasing, this list is automatically sorted by timestamp.

When we get(key, timestamp), we need to find the largest timestamp in the list that is ≤ our query timestamp. This is a classic 'floor' search problem.

Searching for a floor value in a sorted list can be done in O(log n) time using binary search, rather than O(n) time with linear search.

With up to 2e5 operations and potentially many get() calls, this logarithmic speedup is crucial for performance.

Think of organizing historical stock prices by timestamp. If someone asks 'What was the price at 2:30 PM?', you look through your sorted list of timestamps and find the most recent price before or at 2:30 PM.

You don't need to check every single timestamp - you can use the sorted property to quickly narrow down to the right time range. The sorted timestamps are what make this efficient lookup possible.

Use a hash map where each key maps to a list of (timestamp, value) pairs. Since timestamps are strictly increasing per key, each list is automatically sorted by timestamp. For set(), append the new pair to the key's list in O(1) time. For get(), perform binary search on the key's timestamp list to find the largest timestamp ≤ the query timestamp in O(log n) time. This takes advantage of the sorted property to achieve logarithmic lookup time.

• HashMap + Sorted List hybrid structure: When you need to store multiple time-series values per key, combine a HashMap for O(1) key lookup with per-key sorted lists for temporal ordering - this dual-layer structure enables efficient access by both key and time dimension.
• Binary search on timestamps: Since timestamps are strictly increasing per key, use binary search (bisect_right/upper_bound - 1) to find the largest timestamp ≤ query in O(log n) time - this is the floor-finding pattern essential for time-based lookups.
• Monotonic property exploitation: When a problem guarantees strictly increasing timestamps, you can skip insertion sorting and simply append to the list - recognizing monotonic guarantees saves O(n) per insertion and simplifies implementation significantly.
• Off-by-one in binary search: The critical mistake is using bisect_left instead of bisect_right - you need bisect_right then subtract 1 to find the floor timestamp, or check if bisect_left's result has an exact match before using it as the answer.
• Time-series data pattern: This HashMap-of-sorted-arrays pattern applies broadly to versioned data, event logs, stock prices, sensor readings - whenever you need point-in-time queries on historical data with temporal ordering per entity.
• Space-time tradeoff awareness: Storing all historical values costs O(n) space but enables O(log n) queries - understand that precomputing and storing sorted data trades memory for query speed, which is optimal when reads vastly outnumber writes.