LeetCode · #981

Time Based Key-Value Store Solution

Design a data structure that stores key-value pairs with timestamps, and retrieves the value at a given key for the latest timestamp ≤ a query timestamp.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #981

🏗️

Pattern

Design — HashMap + Binary Search

Implement a TimeMap class with: set(key, value, timestamp) — stores the key-value pair at the given timestamp, and get(key, timestamp) — returns the value with the largest timestamp ≤ the given timestamp, or "" if none exists. All set timestamps are strictly increasing.

Example

 TimeMap tm = new TimeMap();
tm.set("foo", "bar", 1);
tm.get("foo", 1); // "bar"
tm.get("foo", 3); // "bar"  (latest ts ≤ 3 is 1)
tm.set("foo", "bar2", 4);
tm.get("foo", 4); // "bar2"
tm.get("foo", 5); // "bar2" (latest ts ≤ 5 is 4) 

Constraints

 • 1 ≤ key.length, value.length ≤ 100 • 1 ≤ timestamp ≤ 10⁷ • All set timestamps are strictly increasing for each key • At most 2 × 10⁵ calls to set and get 

Section Two · Approach 1

Brute Force — Linear Scan O(n)

For each get, scan all entries for the key from newest to oldest and return the first with timestamp ≤ query. O(n) per get where n is the number of entries for that key.

Problem: Linear scan per get with up to 2×10⁵ calls. Since timestamps are inserted in increasing order, the list is already sorted — binary search gives O(log n) per get.

Section Three · Approach 2

HashMap + Binary Search — O(log n) per get

Use a HashMap<String, List<(timestamp, value)>>. Since timestamps for each key are strictly increasing, the list is sorted. For get, binary search for the rightmost timestamp ≤ query (upper bound - 1).

💡 Mental model: Think of a filing cabinet. Each key has its own folder with timestamped pages in chronological order. When someone asks "what was the value at time T?", you flip to the right page using binary search — find the last page with a timestamp not exceeding T.

Algorithm

set(key, value, ts): Append (ts, value) to the key's list.
get(key, ts): Binary search the key's list for the rightmost entry where entry.ts ≤ ts.
If found → return the value. If not (all timestamps > query) → return "".

🎯 Why rightmost (upper bound)?:

We want the latest timestamp that doesn't exceed the query.
This is a "rightmost ≤ target" search — equivalent to upper_bound(ts) - 1 in C++ or bisect_right(ts) - 1 in Python.

Section Four · Trace

Visual Walkthrough

Trace: set("foo","bar",1), set("foo","bar2",4), get("foo",3):

HashMap + Binary Search on timestamp list

Section Five · Implementation

Code — Java & Python

Java — HashMap + Binary Search

 import java.util.*;
class TimeMap {
private Map<String, List<int[]>> tsMap; // int[]{timestamp} private Map<String, List<String>> valMap;
public TimeMap() {
        tsMap = new HashMap<>();
        valMap = new HashMap<>();
    }
public void set(String key, String value, int timestamp) {
        tsMap.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        valMap.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }
public String get(String key, int timestamp) {
if (!tsMap.containsKey(key)) return "";
List<int[]> times = tsMap.get(key);
int left = 0, right = times.size();
while (left < right) { // upper bound int mid = left + (right - left) / 2;
if (times.get(mid)[0] <= timestamp)
                left = mid + 1;
else
right = mid;
        }
if (left == 0) return ""; // all timestamps > query return valMap.get(key).get(left - 1);
    }
}

Python — defaultdict + bisect

 from collections import defaultdict
import bisect
class TimeMap:
def __init__(self):
        self.store = defaultdict(list) # key → [(ts, val), ...] def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
        entries = self.store[key]
# bisect_right on timestamps — find rightmost ts ≤ timestamp
i = bisect.bisect_right(entries, (timestamp, chr(127)))
if i == 0: return "" return entries[i - 1][1]

Section Six · Analysis

Complexity Analysis

Operation	Time	Space
set	O(1) amortized	O(1) per call
get (linear scan)	O(n)	O(1)
get (binary search) ← optimal	O(log n)	O(1)

Total space: O(S) where S = total number of set calls. Each call stores one (timestamp, value) pair.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Scenario	Why It Matters
Key not found	get("unknown", 1)	Key doesn't exist in map → return "".
Timestamp too early	set at ts=5, get at ts=3	No entry ≤ 3 → return "".
Exact match	set at ts=5, get at ts=5	Binary search finds exact timestamp → return its value.
Many entries	10⁵ sets for one key	Binary search handles large lists in ~17 comparisons.

⚠ Common Mistake: Using bisect_left instead of bisect_right (or equivalent). We want the rightmost entry ≤ timestamp. bisect_right finds the first index after all entries ≤ timestamp — subtract 1 to get the answer. bisect_left would miss the exact-match case when there are additional concerns.

← Back to Binary Search problems

LearningTree

LC 981 · Time Based Key-Value Store — Solution & Explanation | DSA Guide