Problem Description

You need to design a time-based key-value data structure that can store values with timestamps and retrieve them based on timestamp queries.

The data structure should support the following operations:

1. Initialize: Create an empty TimeMap object.

2. Set operation: Store a key-value pair along with a timestamp. The method set(key, value, timestamp) takes:

   • key: a string identifier
   • value: a string value to store
   • timestamp: an integer representing when this value was stored

3. Get operation: Retrieve a value for a given key at or before a specific timestamp. The method get(key, timestamp) should:

   • Find the value that was set with the largest timestamp less than or equal to the given timestamp
   • Return that value if it exists
   • Return an empty string "" if no such value exists

Key characteristics:

• Multiple values can be stored for the same key at different timestamps
• When querying, you want the most recent value that doesn't exceed the query timestamp
• If the query timestamp is earlier than any stored timestamp for that key, return ""
• The timestamps for each key are guaranteed to be set in strictly increasing order (this is implied by the solution's use of binary search)

Example scenario: If you set ("foo", "bar1", 1) and ("foo", "bar2", 4), then:

• get("foo", 3) returns "bar1" (timestamp 1 ≤ 3, and it's the latest available)
• get("foo", 5) returns "bar2" (timestamp 4 ≤ 5, and it's the latest available)
• get("foo", 0) returns "" (no timestamp ≤ 0)

Intuition

The core challenge is efficiently finding the most recent value that doesn't exceed a given timestamp. This naturally suggests we need to maintain some ordering of timestamps for each key.

Let's think about what happens when we store values:

• Each key can have multiple values at different timestamps
• We need to keep track of both the timestamp and value together
• The timestamps are inserted in increasing order (a critical observation)

For retrieval, we need to find the largest timestamp that is ≤ the query timestamp. This is essentially asking: "What's the most recent value before or at this time?"

This problem pattern - finding the largest element not exceeding a target value in a sorted collection - is a classic binary search scenario. Since timestamps come in increasing order, we can maintain a sorted list of (timestamp, value) pairs for each key.

The key insight is using a hash table where:

• Keys map to lists of (timestamp, value) tuples
• These lists remain sorted by timestamp naturally (since timestamps are inserted in increasing order)

For the get operation, we can use binary search to find the right position. Specifically, we want to find where our query timestamp would fit in the sorted list, then look at the element just before that position. This gives us the largest timestamp ≤ our query.

The solution uses bisect_right with a clever trick: searching for (timestamp, chr(127)). Since chr(127) is the highest ASCII character, this tuple will be greater than any (timestamp, actual_value) pair with the same timestamp. bisect_right returns the insertion point after all equal elements, so we get the position right after the last valid timestamp. Subtracting 1 gives us the desired element.

If the returned index is 0, it means no timestamp is ≤ our query timestamp, so we return an empty string.

Learn more about Binary Search patterns.

Solution Approach

The solution uses a hash table combined with binary search to efficiently store and retrieve time-based key-value pairs.

Data Structure Design

We use a defaultdict(list) called ktv (key-timestamp-value) where:

• Each key maps to a list of tuples (timestamp, value)
• The list for each key remains sorted by timestamp since insertions happen in chronological order

Implementation Details

1. Initialization (__init__)

self.ktv = defaultdict(list)

Creates an empty hash table that automatically initializes new keys with empty lists.

2. Set Operation (set)

self.ktv[key].append((timestamp, value))

Simply appends the (timestamp, value) tuple to the list for the given key. Since timestamps are guaranteed to be in increasing order, the list remains sorted without any additional work.

3. Get Operation (get)

The retrieval uses binary search to find the appropriate value:

if key not in self.ktv:
    return ''
tv = self.ktv[key]
i = bisect_right(tv, (timestamp, chr(127)))
return tv[i - 1][1] if i else ''

Let's break down the binary search logic:

• First, check if the key exists; return empty string if not
• bisect_right(tv, (timestamp, chr(127))) finds the insertion point for our search tuple
• Why chr(127)? When comparing tuples, Python compares element by element. Since chr(127) is the highest ASCII character, (timestamp, chr(127)) will be greater than any (timestamp, actual_value) pair with the same timestamp
• bisect_right returns the index where we'd insert to maintain sorted order - this is the position after all elements with timestamp ≤ our query timestamp
• If i > 0, then tv[i-1] contains the largest timestamp not exceeding our query, so we return tv[i-1][1] (the value part)
• If i == 0, no timestamp is small enough, so we return empty string

Time Complexity

• set: O(1) - simple append operation
• get: O(log n) where n is the number of timestamps for the key - binary search
• Space: O(m × n) where m is the number of unique keys and n is the average number of timestamps per key

The solution elegantly leverages the fact that timestamps arrive in order, eliminating the need for sorting while maintaining the ability to perform efficient binary searches.

Example Walkthrough

Let's walk through a concrete example to see how the TimeMap works:

Step 1: Initialize and Set Values

tm = TimeMap()
tm.set("user1", "active", 1)
tm.set("user1", "away", 3)
tm.set("user1", "offline", 7)

After these operations, our internal data structure looks like:

ktv = {
    "user1": [(1, "active"), (3, "away"), (7, "offline")]
}

Step 2: Query at timestamp 5

result = tm.get("user1", 5)

Let's trace through the binary search:

• We have the list: [(1, "active"), (3, "away"), (7, "offline")]
• We search for (5, chr(127)) using bisect_right
• Binary search compares:
  • (5, chr(127)) vs (3, "away"): Since 5 > 3, look right
  • (5, chr(127)) vs (7, "offline"): Since 5 < 7, we found our insertion point
• bisect_right returns index 2 (where we'd insert to keep sorted order)
• We return tv[2-1][1] = tv[1][1] = "away"

Step 3: Query at timestamp 10

result = tm.get("user1", 10)

• Search for (10, chr(127)) in [(1, "active"), (3, "away"), (7, "offline")]
• Since 10 is greater than all timestamps, bisect_right returns index 3
• We return tv[3-1][1] = tv[2][1] = "offline"

Step 4: Query at timestamp 0

result = tm.get("user1", 0)

• Search for (0, chr(127)) in [(1, "active"), (3, "away"), (7, "offline")]
• Since 0 is less than all timestamps, bisect_right returns index 0
• Since index is 0, we return "" (no valid value exists)

Step 5: Add another key and query

tm.set("user2", "online", 2)
result = tm.get("user2", 5)

Now our structure is:

ktv = {
    "user1": [(1, "active"), (3, "away"), (7, "offline")],
    "user2": [(2, "online")]
}

• For get("user2", 5):
• Search for (5, chr(127)) in [(2, "online")]
• bisect_right returns index 1 (after the single element)
• We return tv[1-1][1] = tv[0][1] = "online"

This example demonstrates how the binary search efficiently finds the most recent value not exceeding the query timestamp, handling edge cases like queries before the first timestamp or after the last timestamp.

Solution Implementation

Time and Space Complexity

Time Complexity:

• set operation: O(1) - The operation appends a tuple to a list stored in a hash table. Hash table access is O(1) and list append is O(1) amortized, resulting in overall O(1) time complexity.

• get operation: O(log n) where n is the number of timestamps stored for a given key. The operation involves:

  • Hash table lookup: O(1)
  • Binary search using bisect_right: O(log n)
  • Overall: O(log n)

Space Complexity:

• O(n) where n is the total number of set operations performed. Each set operation stores a new (timestamp, value) tuple in the hash table, and all these entries are maintained in memory. The hash table itself and the lists within it collectively require space proportional to the number of stored entries.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using bisect_left Instead of bisect_right

The Issue: A common mistake is using bisect_left instead of bisect_right. This can lead to incorrect results when dealing with exact timestamp matches.

Why it's wrong:

# Incorrect approach
insertion_index = bisect_left(time_value_list, (timestamp, ''))
return time_value_list[insertion_index][1] if insertion_index < len(time_value_list) and time_value_list[insertion_index][0] <= timestamp else ''

This fails because:

• bisect_left returns the leftmost insertion point
• You'd need additional logic to check if the found element's timestamp is actually <= the query timestamp
• The code becomes more complex and error-prone

The correct solution uses bisect_right:

insertion_index = bisect_right(time_value_list, (timestamp, chr(127)))
return time_value_list[insertion_index - 1][1] if insertion_index else ''

Pitfall 2: Incorrect Tuple Comparison in Binary Search

The Issue: Using just the timestamp for binary search without considering tuple comparison rules:

# Incorrect - might not handle edge cases properly
insertion_index = bisect_right([t for t, v in time_value_list], timestamp)

Why it's wrong:

• This creates an unnecessary list comprehension
• Loses the direct mapping between index and value
• Less efficient due to list creation

The solution: Use a tuple with a sentinel value chr(127) to ensure proper comparison. When Python compares tuples, it compares element by element, so (timestamp, chr(127)) will always be greater than any (timestamp, actual_value) with the same timestamp.

Pitfall 3: Not Handling Empty Results Correctly

The Issue: Forgetting to check if the binary search returns index 0:

# Incorrect - will cause index error or return wrong value
insertion_index = bisect_right(time_value_list, (timestamp, chr(127)))
return time_value_list[insertion_index - 1][1]  # Fails when insertion_index is 0

Why it's wrong:

• When insertion_index is 0, it means all stored timestamps are greater than the query timestamp
• Accessing time_value_list[-1] would incorrectly return the last element

The solution: Always check if insertion_index is 0 before accessing the previous element:

return time_value_list[insertion_index - 1][1] if insertion_index else ''

Pitfall 4: Not Leveraging the Sorted Nature of Timestamps

The Issue: Attempting to sort the list on each insertion or retrieval:

# Inefficient approach
def set(self, key, value, timestamp):
    self.ktv[key].append((timestamp, value))
    self.ktv[key].sort()  # Unnecessary!

Why it's wrong:

• The problem guarantees timestamps are inserted in strictly increasing order
• Sorting adds O(n log n) complexity to each insertion
• Wastes computational resources

The solution: Trust the problem constraints and simply append to the list. The list naturally maintains sorted order due to the timestamp guarantee.