Repository navigation
063 — Time Based Key Value Store
LeetCode 981 · Medium. Design a time-based key-value store that can store multiple values for the same key at different time stamps, and retrieve the key's value at a certain timestamp. Implement TimeMap with set(key, value, timestamp), which stores the key with the value at the given timestamp, and get(key, timestamp), which returns the value associated with key at the largest stored timestamp that is <= timestamp, or "" if there is none. Calls to set for a given key are guaranteed to happen in strictly increasing order of timestamp.
This is two data structures snapped together, each doing the job it's best at. A hash map handles "which key" — O(1) to find the right bucket of (timestamp, value) pairs for a given key. But once you're inside that bucket, "which timestamp" is a different question entirely, and because set calls for one key always arrive with strictly increasing timestamps, that bucket is already sorted the moment it's built — no separate sort step needed. A sorted list plus "find the largest entry <= some value" is exactly the shape Binary Search wants: it's the same "find the insertion point" idea as a plain sorted-array search, just phrased as "find the rightmost timestamp that still qualifies" instead of "find an exact match."
"Store values by key and timestamp, retrieve the value at (or most recently before) a given timestamp" signals a hash map for the key dimension, layered with a search over a time-ordered sequence for the timestamp dimension. The phrase "largest timestamp <= given timestamp" is the real cue for Binary Search specifically — it's a floor/predecessor search over a sorted sequence, not an exact-match lookup, so the algorithm needs to remember the best candidate seen so far and keep probing for something even closer, rather than stopping the instant it finds a match.
Store each key's (timestamp, value) pairs in an array, and on get, scan every stored entry for that key to find the one with the largest timestamp that still qualifies.
class TimeMapBruteForce {
private var store: [String: [(timestamp: Int, value: String)]] = [:]
func set(_ key: String, _ value: String, _ timestamp: Int) {
store[key, default: []].append((timestamp, value))
}
func get(_ key: String, _ timestamp: Int) -> String {
guard let entries = store[key] else { return "" }
var bestValue = ""
var bestTimestamp = -1
for entry in entries where entry.timestamp <= timestamp {
if entry.timestamp > bestTimestamp {
bestTimestamp = entry.timestamp
bestValue = entry.value
}
}
return bestValue
}
}
// smoke test
let bruteMap = TimeMapBruteForce()
bruteMap.set("foo", "bar", 1)
print(bruteMap.get("foo", 1)) // "bar"
print(bruteMap.get("foo", 3)) // "bar"
bruteMap.set("foo", "bar2", 4)
print(bruteMap.get("foo", 4)) // "bar2"
print(bruteMap.get("foo", 5)) // "bar2"
print(bruteMap.get("foo", 0)) // ""Big-O: set is O(1) amortized. get is O(m), where m is the number of entries stored for that key — it re-scans the whole list every call, ignoring that the list happens to be time-ordered. O(n) total space for n stored entries.
Keep the same hash map of per-key arrays, but exploit that each array is already sorted by timestamp (a guarantee of the problem, not something the code has to enforce): binary search each get for the rightmost entry with timestamp <= timestamp.
class TimeMap {
private var store: [String: [(timestamp: Int, value: String)]] = [:]
func set(_ key: String, _ value: String, _ timestamp: Int) {
store[key, default: []].append((timestamp, value))
}
func get(_ key: String, _ timestamp: Int) -> String {
guard let entries = store[key], !entries.isEmpty else { return "" }
var lo = 0
var hi = entries.count - 1
var result = ""
while lo <= hi {
let mid = lo + (hi - lo) / 2
if entries[mid].timestamp <= timestamp {
result = entries[mid].value // valid candidate — keep searching right for something closer
lo = mid + 1
} else {
hi = mid - 1
}
}
return result
}
}
// smoke test
let timeMap = TimeMap()
timeMap.set("foo", "bar", 1)
print(timeMap.get("foo", 1)) // "bar"
print(timeMap.get("foo", 3)) // "bar"
timeMap.set("foo", "bar2", 4)
print(timeMap.get("foo", 4)) // "bar2"
print(timeMap.get("foo", 5)) // "bar2"
print(timeMap.get("foo", 0)) // ""Big-O: set is O(1) amortized. get is O(log m), where m is the number of entries stored for that key. O(n) total space for n stored entries.
The brute force's get re-derives "which entry is best" from scratch every call by looking at all of them, even though the list never needs re-sorting — the problem's own guarantee (set timestamps arrive in increasing order per key) means the array is sorted for free at insertion time. Once you recognize a list is already sorted, scanning it linearly to answer a "largest value <= X" question is leaving the sortedness on the table; Binary Search answers the identical question by keeping a running best candidate while it discards half of the remaining entries every step, the same floor/predecessor variant of binary search used to find insertion points in a plain sorted array.
-
Hash Maps & Hash Sets — the outer structure, mapping each key to its own list of timestamped values in
O(1). -
Arrays & Strings — each key's bucket is a plain array, kept sorted by timestamp because
setcalls arrive in increasing order. -
Binary Search — the floor-search variant used inside
get, tracking the best-so-far candidate while still halving the search space each step.
Time Based Key-Value Store is a hash map for "which key" layered over a binary search for "which moment in time" — the per-key list is already sorted the moment it's built, so get just floor-searches it.
For key "foo" with stored entries (timestamp: 2, value: "a"), (timestamp: 5, value: "b"), (timestamp: 9, value: "c"), trace the optimal get's lo/hi/mid and the running result for get("foo", 7). Why does the algorithm keep narrowing (lo = mid + 1) instead of stopping immediately after finding a qualifying entry at mid?
⬅️ Previous: Find Minimum in Rotated Sorted Array · Next: Median of Two Sorted Arrays ➡️