LeetEye LeetEye
Medium Binary Search ~5 min

Time Based Key-Value Store

binary-search time-based-key-value-store

Problem

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:
- TimeMap() Initializes the object.
- void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
- String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Examples

Example 1
Input: nums = [1,2,3]
Output: result
Key Insight

Timestamps are always increasing. Store (timestamp, value) pairs per key in sorted order. Binary search for largest timestamp ≤ query.

Store (timestamp, value) pairs per key. Timestamps increase so list stays sorted. Binary search for largest timestamp ≤ query.

How to Approach This Problem

Pattern Recognition: When you see keywords like time based key-value store binary-search, think Binary Search.

Step-by-Step Reasoning

1 To map keys to their history, use:
Answer: Hash map with key → list of (timestamp, value)
Need O(1) key lookup. Each key has multiple (timestamp, value) pairs.
2 The constraint "timestamps are strictly increasing" means:
Answer: Appending maintains sorted order
New timestamps are always larger, so appending naturally keeps list sorted.
3 get(key, timestamp) should return:
Answer: Value with largest timestamp ≤ query
"Most recent before or at this time" = largest timestamp that doesn't exceed query.
4 We need binary search to find:
Answer: Rightmost timestamp ≤ query (upper bound - 1)
We want the largest timestamp not exceeding query. This is floor/predecessor search.
5 If no timestamp ≤ query exists:
Answer: Return empty string
Problem states to return "" if no valid timestamp found.
6 With n entries for a key, get() takes:
Answer: O(log n)
Binary search on sorted list of timestamps.

Solution

class TimeMap:
    def __init__(self):
        self.store = {}  # key -> [(timestamp, value), ...]
    
    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))
    
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        
        values = self.store[key]
        left, right = 0, len(values) - 1
        result = ""
        
        while left <= right:
            mid = left + (right - left) // 2
            if values[mid][0] <= timestamp:
                result = values[mid][1]
                left = mid + 1
            else:
                right = mid - 1
        
        return result

Complexity Analysis

Time set: O(1), get: O(log n)
Space O(total entries)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye