Domain 2MediumMEDIUM

Time Based Key-Value Store

Implement a time-based key-value store using a hash map where each value maps to a sorted list of timestamps and values, enabling O(log N) retrieval via binary search.

Domain: medium•Updated: 2026-09-05
#hash map#binary search

Problem Breakdown

We need to implement a TimeMap class that stores key-value pairs with associated timestamps. The core operations are:

  1. set(key, value, timestamp): Stores the entry. Timestamps for all set operations are strictly increasing globally.
  2. get(key, timestamp): Returns the latest stored value where its timestamp is less than or equal to the given timestamp. If no such value exists (key missing or timestamps too new), return an empty string ("").

Key Constraints:

  • Timestamps for all set operations are strictly increasing (t1<t2<…t_1 < t_2 < \dots). This guarantees that entries stored in a list per-key remain sorted by timestamp without explicit sorting.
  • Total number of calls (set + get) is up to 120,000. An O(N)O(N) linear scan for get would lead to Time Limit Exceeded (TLE), so we need logarithmic time complexity for retrieval.

Intuition

Since timestamps are strictly increasing globally across all operations, any list of entries associated with a specific key will naturally be sorted by timestamp in the order they were inserted into our data structure.

The problem reduces to finding the largest stored timestamp that is less than or equal to the query timestamp. In a sorted array (or list), this corresponds to an “upper bound” search where we want the rightmost element satisfying the condition ≤\le target.

A naive linear scan for each get operation would take O(K)O(K) time, leading to quadratic behavior in worst-case scenarios with many queries on hot keys. By using Binary Search (specifically finding the upper bound), we can reduce this lookup to O(log⁡K)O(\log K). We use a Hash Map (dict) where keys map to lists of [timestamp, value] tuples for efficient key access (O(1)O(1)).

Approach

  1. Initialization: Initialize an empty dictionary self.store. This maps each string key to a list containing pairs of [timestamp, value].
  2. set Operation:
    • If the key does not exist in store, create a new entry (list).
    • Append the current [timestamp, value] pair to the existing list for that key. Because timestamps are strictly increasing globally, this maintains sorted order automatically without needing sort operations inside set.
  3. get Operation:
    • Check if the key exists in store. If not, return "".
    • Retrieve the list of entries for the key.
    • Perform Binary Search to find the rightmost index where entry[timestamp] <= query_timestamp.
      • Initialize pointers left = 0, right = len(entries) - 1.
      • Maintain a variable (e.g., ans_idx) initialized to -1 to track valid candidates.
      • While loop: Calculate mid. If entries[mid][timestamp] <= query_timestamp, record index and move right (left = mid + 1). Else, move left (right = mid - 1).
    • Return the value at ans_idx if found; otherwise return "".

Complexity Analysis

  • Time Complexity:
    • set: O(1)O(1) amortized (hash map insertion and list append).
    • get: O(log⁡K)O(\log K) where KK is the number of entries for that specific key. Since total operations are bounded, this ensures efficiency within limits (N≤120,000N \le 120,000).
  • Space Complexity:
    • O(N)O(N), where NN is the total number of elements stored across all keys (sum of lengths of lists in self.store).

Solution

class TimeMap:

    def __init__(self):
        # Map key -> list of [timestamp, value]
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        
        # Append new entry. Timestamps are strictly increasing globally, 
        # so the list remains sorted by timestamp automatically.
        self.store[key].append([timestamp, value])

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store or len(self.store[key]) == 0:
            return ""
        
        entries = self.store[key]
        left, right = 0, len(entries) - 1
        
        # Binary search to find the largest index where entry[timestamp] <= query_timestamp
        ans_idx = -1
        
        while left <= right:
            mid = (left + right) // 2
            
            if entries[mid][0] <= timestamp:
                ans_idx = mid      # Valid candidate found, try to go newer
                left = mid + 1     # Move search space to the right
            else:
                right = mid - 1    # Current entry is too new
        
        return "" if ans_idx == -1 else entries[ans_idx][1]

Edge Cases Handled

  • Key Not Found: The get method checks if the key exists in self.store. If missing, it immediately returns an empty string.
  • Timestamp Smaller than All Entries: Binary search logic sets ans_idx = -1 initially. If all stored timestamps are greater than the query timestamp (e.g., first entry is at t=5t=5, query is t=3t=3), the condition entries[mid][0] <= timestamp will never be met, leaving ans_idx as -1. The method returns "".
  • Exact Timestamp Match: If a stored value exists exactly at the requested timestamp (e.g., entry [5, "val"], query t=5t=5), the condition holds. Binary search continues to try finding something newer (left = mid + 1). Since no later entries exist for that exact time or are older but valid, it returns the correct value associated with timestamp.
  • Empty Store: If a key has been set once and then queried before any subsequent sets (or if store is empty), logic handles list length checks.