Time-Based Key-Value Store LeetCode 981

LeetCode 981, Time Based Key-Value Store, asks you to design a data structure with two operations: set(key, value, timestamp) stores the value associated with a key at a given timestamp, and get(key, timestamp) returns the value stored for key at the largest timestamp less than or equal to the given timestamp. If no such value exists, return an empty string.

The challenge is that multiple values can be stored for the same key at different timestamps, and get must find the most recent one that does not exceed the query timestamp. A naive scan through all stored values for a key would be O(n) per query, which is too slow when the store accumulates millions of entries.

The constraints that make the problem tractable are: timestamps passed to set are strictly increasing for each key, all timestamps are positive integers up to 10^7, and key and value lengths are at most 100 characters. The strictly-increasing timestamp guarantee is the key insight that enables an efficient solution without explicit sorting.

A simple HashMap<String, String> would give O(1) set and O(1) get if we only needed the latest value. But get must find the value with the largest timestamp that does not exceed the query — this is a range query, not an exact lookup. A plain HashMap cannot answer range queries without scanning all entries for a key.

What we need is sorted storage per key so that we can binary search for the correct timestamp. The naive approach of keeping a sorted list and running a linear scan would be O(n) per get. Binary search on the sorted list brings this down to O(log n), which is fast enough for the given constraints.

The key realization is that we do not need a general sorted map — we just need the list of (timestamp, value) pairs for each key to be in timestamp order so we can binary search it. Since timestamps are strictly increasing per key by the problem guarantee, the list is already in sorted order by the time any get query arrives.

The optimal data structure is a HashMap where each key maps to a list of (timestamp, value) pairs. In Python this is a defaultdict(list); in Java it is a HashMap<String, List<int[]>> or HashMap<String, List<long[]>>. The list for each key grows by one entry with every set call.

The set operation simply appends (timestamp, value) to the list for the given key. Because timestamps are strictly increasing, the list remains sorted in ascending order of timestamp without any explicit sorting step. This gives set O(1) amortized time and O(1) space per call.

The get operation binary searches the list for the given key to find the largest timestamp that does not exceed the query timestamp. If the key does not exist in the map at all, return an empty string immediately. If it exists but all stored timestamps are greater than the query, also return an empty string.

The get operation performs a binary search on the list of (timestamp, value) pairs for the given key. We want the rightmost entry whose timestamp is less than or equal to the query timestamp. This is equivalent to finding the insertion point of the query timestamp and stepping one position back.

In Python, bisect_right(timestamps, query) returns the index where query would be inserted to keep the list sorted, counting from the right for duplicates. The entry just before that index — at position bisect_right(...) - 1 — is the largest stored timestamp that does not exceed query. If the result is 0, no valid entry exists and we return an empty string.

In Java, Collections.binarySearch returns a non-negative index for an exact match or -(insertion point) - 1 for a miss. For an exact match, return that value. For a miss, the insertion point is (-result - 1), and the answer is at insertion point - 1 (if >= 0). Alternatively, use TreeMap<Integer, String> with floorKey(timestamp) for a cleaner one-liner.

Java's TreeMap<Integer, String> with floorKey(timestamp) provides a clean alternative. Store a HashMap<String, TreeMap<Integer, String>> where the inner TreeMap maps timestamps to values. The set operation is map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value). The get operation is map.getOrDefault(key, new TreeMap<>()).floorKey(timestamp), which returns null if no valid timestamp exists.

Python's sortedcontainers library provides SortedDict, which offers similar O(log n) key lookup with bisect_left and bisect_right semantics built in. SortedDict.irange can also return an iterator over a key range. Both TreeMap and SortedDict give the same asymptotic complexity but with slightly higher constant factors than a plain list with bisect due to tree overhead.

For interview purposes, the list-plus-bisect approach is often preferred in Python because it uses only the standard library and is simpler to explain. The TreeMap approach is natural and idiomatic in Java. Both are perfectly acceptable — choose the one you can code and explain most clearly under pressure.

Python with defaultdict and bisect: self.store = defaultdict(list). In set, self.store[key].append((timestamp, value)). In get, if key not in self.store return "". Extract the timestamps with a list comprehension or keep a parallel list. Use idx = bisect_right(timestamps, timestamp); return self.store[key][idx-1][1] if idx > 0 else "". Time: O(1) set, O(log n) get. Space: O(n) total.

Java with ArrayList and Collections.binarySearch: Map<String, List<int[]>> store = new HashMap<>(). In set, store.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp, ...value...}). In get, if no list return "". Use Collections.binarySearch with a custom comparator for the timestamp field; compute the insertion point and retrieve index - 1 if >= 0.

Both implementations achieve O(1) amortized set and O(log n) get. The total space is O(n) where n is the total number of set calls. The binary search is the only non-trivial part — once you have the sorted list guarantee from strictly increasing timestamps, the rest of the logic is straightforward index arithmetic.

Time Based Key-Value Store belongs to the data structure design family on LeetCode. Design Hit Counter (LeetCode 362) uses a similar time-windowed storage problem: count hits in the last 5 minutes, which can be solved with a deque or circular buffer rather than binary search, but shares the idea of storing timestamped events efficiently.

The binary search technique used in get is the same rightmost-valid-entry search that appears throughout the binary search patterns family. Find Minimum in Rotated Sorted Array (LeetCode 153) and problems requiring answer-space binary search all rely on finding a boundary condition. Recognizing that get is a boundary-search problem — largest timestamp not exceeding query — is the key conceptual leap.

Versioned data structures are a broader design theme. Implement Trie (LeetCode 208) and Add and Search Word (LeetCode 211) are design problems that require careful choice of data structure per operation complexity. Time Based Key-Value Store adds the dimension of time, making it a versioned key-value store — a pattern that appears in databases, distributed systems, and MVCC (multi-version concurrency control) implementations in the real world.