981. Time Based Key-Value Store

At a Glance

• Topic: binary-search
• Pattern: Binary Search (Prefix / latest ≤ timestamp)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Uber
• Frequency: High
• LeetCode: 981

Problem (one-liner)

Design set(key, value, timestamp) and get(key, timestamp) returning the value for key whose stored timestamp is the largest still ≤ timestamp; if none, return "". Timestamps for a given key arrive strictly increasing on set.

Recognition Cues

• Time series per key
• “Latest at or before” query — prefix maximum on sorted timestamps
• Monotonic inserts → per-key slice stays sorted → binary search

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n) get — scan all pairs for key.
• Better — map key → list + linear scan from end — O(k) per get for k events of key.
• Optimal — O(log k) get, O(1) amortized set — hash map of append-only vectors + upper-bound style BS for last ≤ timestamp.

Optimal Solution

Go

type timeValue struct {
	timestamp int
	value     string
}

type TimeMap struct {
	data map[string][]timeValue
}

func Constructor() TimeMap {
	return TimeMap{data: make(map[string][]timeValue)}
}

func (timeMap *TimeMap) Set(key string, value string, timestamp int) {
	timeMap.data[key] = append(timeMap.data[key], timeValue{timestamp: timestamp, value: value})
}

func (timeMap *TimeMap) Get(key string, timestamp int) string {
	pairs, exists := timeMap.data[key]
	if !exists {
		return ""
	}
	left, right := 0, len(pairs)-1
	best := -1
	for left <= right {
		mid := left + (right-left)/2
		if pairs[mid].timestamp <= timestamp {
			best = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if best == -1 {
		return ""
	}
	return pairs[best].value
}

JavaScript

class TimeMap {
	constructor() {
		this.data = new Map();
	}

	set(key, value, timestamp) {
		if (!this.data.has(key)) {
			this.data.set(key, []);
		}
		this.data.get(key).push({ timestamp, value });
	}

	get(key, timestamp) {
		const pairs = this.data.get(key);
		if (!pairs || pairs.length === 0) {
			return '';
		}
		let left = 0;
		let right = pairs.length - 1;
		let best = -1;
		while (left <= right) {
			const mid = left + Math.floor((right - left) / 2);
			if (pairs[mid].timestamp <= timestamp) {
				best = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return best === -1 ? '' : pairs[best].value;
	}
}

Walkthrough

After set("foo","high",10) and set("foo","low",3), get("foo",4) uses timestamps [3,10] — search last ≤ 4 → index 0 → "low".

Invariant: per-key timestamps strictly increase, so each slice is sorted and binary search is valid.

Edge Cases

• get before any set for key — empty.
• timestamp before first event — "".
• Exact hit on stored timestamp.

Pitfalls

• Using strict < for “at or before” — need <= in comparison and track last valid index.
• Storing unsorted times — breaks binary search; rely on problem’s monotonic set order.

Similar Problems

• 35. Search Insert Position — same lower/upper bound reasoning on sorted array.
• 704. Binary Search — core midpoint loop.
• 875. Koko Eating Bananas — binary search on a monotone predicate over a timeline of decisions.

Variants

• Non-monotonic inserts — sort per get (expensive) or use tree map.
• Integer timestamps only — can compress to index order.

Mind-Map Tags

#binary-search #time-series #prefix-max #map-of-vectors