#981

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Time Based Key-Value Store

Implement a time-based key-value store that retrieves the latest value at a given timestamp using efficient binary search techniques.

hash table string binary search design

Problem Statement

Design a data structure called TimeMap that supports storing multiple values for the same key at different timestamps and retrieving the key's value at a given timestamp. Each key can have several values, but queries should return the most recent value no later than the requested timestamp.

Implement the following operations: set(key, value, timestamp) which stores the value along with its timestamp, and get(key, timestamp) which returns the value set at or before the timestamp. If no such value exists, return an empty string. All timestamps are strictly increasing for each key.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

Constraints

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 107
All the timestamps timestamp of set are strictly increasing.
At most 2 * 105 calls will be made to set and get.

Solution Approach

Use a Hash Map to Store Timestamped Values

Maintain a hash map where each key maps to a list of (timestamp, value) pairs. This allows O(1) access to the key's history and ensures that all timestamped values are stored in strictly increasing order, which is essential for applying binary search during retrieval.

Binary Search Over the Timestamp List

When retrieving a value for a given timestamp, perform binary search on the list of stored timestamps for that key. This efficiently finds the largest timestamp less than or equal to the query, avoiding linear scans and ensuring O(log n) query time per key.

Handle Edge Cases and Nonexistent Keys

If a key does not exist or the query timestamp is earlier than any stored timestamp, return an empty string. Ensure that the search correctly handles the boundary conditions, as failing to do so is a common source of errors in this problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Setting a value is O(1) because it appends to a list. Getting a value requires O(log n) binary search where n is the number of timestamps for that key. Space complexity is O(m) where m is the total number of set operations stored across all keys.

What Interviewers Usually Probe

Ask if you can assume timestamps are strictly increasing per key.
Check if the candidate uses binary search instead of linear scan for retrieval.
Confirm handling of keys with no stored value at the queried timestamp.

Common Pitfalls or Variants

Common pitfalls

Performing linear search instead of binary search for get operations, leading to timeouts.
Not handling empty lists or keys with no stored timestamps properly.
Incorrectly implementing binary search boundaries, returning the wrong value for edge timestamps.

Follow-up variants

Support deletion of key-value pairs at specific timestamps.
Allow multiple keys with overlapping timestamp ranges and query across them.
Retrieve all values within a given timestamp range instead of just the latest one.

FAQ

Why do we need binary search in Time Based Key-Value Store?

Binary search efficiently finds the most recent value at or before the given timestamp, avoiding a slow linear scan over all stored values for a key.

Can timestamps be repeated for the same key?

No, timestamps are strictly increasing for each key, which ensures that each binary search retrieves a unique latest value.

What should get return if no value exists at the query timestamp?

It should return an empty string if the key doesn't exist or the query timestamp is earlier than any stored timestamp.

How does GhostInterview help with edge cases?

It points out boundary conditions, such as querying before the first timestamp or at exact timestamp matches, ensuring correct implementation.

What is the space complexity for storing Time Based Key-Value data?

Space complexity is O(m), where m is the total number of set operations across all keys, because each (timestamp, value) pair is stored.

terminal

Solution

Solution 1: Hash Table + Ordered Set (or Binary Search)

We can use a hash table $\textit{kvt}$ to record key-value pairs, where the key is the string $\textit{key}$ and the value is an ordered set. Each element in the set is a tuple $(\textit{timestamp}, \textit{value})$, representing the value $\textit{value}$ corresponding to the key $\textit{key}$ at the timestamp $\textit{timestamp}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class TimeMap:
    def __init__(self):
        self.ktv = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.ktv[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.ktv:
            return ''
        tv = self.ktv[key]
        i = bisect_right(tv, (timestamp, chr(127)))
        return tv[i - 1][1] if i else ''


# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)

Continue Practicing

#911 online election #1146 snapshot array #792 number of matching subsequences