LeetCode: 981 Binary Search in `Time Based Key-Value Store`

LeetCode 981: Time Based Key-Value Store

Explanation of Binary Search in Time Based Key-Value Store

If we are not allowed to use bisect.bisect_right(values, (timestamp, chr(127))), we can manually implement binary search to achieve the same result. Below is a solution that uses a custom binary search to find the closest timestamp less than or equal to the given timestamp.

Code with Manual Binary Search

from collections import defaultdict

class TimeMap:

    def __init__(self):
        # Use defaultdict to store each key's (timestamp, value) list
        self.time_map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        # Add (timestamp, value) to the list associated with the key
        self.time_map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        # If the key doesn't exist, return an empty string
        if key not in self.time_map:
            return ""

        # Get all (timestamp, value) pairs for the key
        values = self.time_map[key]

        # Perform a manual binary search to find the largest timestamp less than or equal to the given timestamp
        return self.binary_search(values, timestamp)

    def binary_search(self, values: list, timestamp: int) -> str:
        left, right = 0, len(values) - 1
        idx = -1  # Initialize idx, indicating the closest timestamp found

        while left <= right:
            mid = (left + right) // 2

            # If the current timestamp is less than or equal to the given timestamp, it might be the answer
            if values[mid][0] <= timestamp:
                idx = mid  # Store the current index
                left = mid + 1  # Move the left boundary to continue searching for a larger timestamp
            else:
                right = mid - 1  # The current timestamp is too large, move to the left

        # If a valid timestamp is found, return the corresponding value; otherwise, return an empty string
        if idx == -1:
            return ""
        else:
            return values[idx][1]

Code Explanation

1. set method:

   • This part remains unchanged from the original solution. It adds the (timestamp, value) pair to the list associated with the given key in time_map.

2. get method:

   • First, it checks if the key exists. If not, it returns an empty string "".
   • If the key exists, it uses the binary_search method to find the closest timestamp less than or equal to the given timestamp.

3. binary_search method:

   • The goal of binary search here is to find the largest timestamp that is less than or equal to the given timestamp. The values list contains (timestamp, value) pairs, which are sorted by timestamp.
   • We use the binary search technique:
     • If values[mid][0] <= timestamp, we store the current index as a candidate result and continue searching for a larger valid timestamp on the right side (left = mid + 1).
     • If values[mid][0] > timestamp, we search the left side (right = mid - 1).
   • After the loop, if a valid timestamp is found (idx != -1), the corresponding value is returned; otherwise, an empty string is returned.

Complexity Analysis

• Time Complexity:

  • The set operation is O(1) because appending to the list takes constant time.
  • The get operation takes O(log n) time, where n is the number of timestamps for the given key, since binary search is used.

• Space Complexity: O(n), where n is the total number of (timestamp, value) pairs stored across all keys.

Example

Let’s see how this works with an example:

kv = TimeMap()
kv.set("foo", "bar", 1)   # Store "foo" with value "bar" at timestamp 1
kv.set("foo", "bar2", 4)  # Store "foo" with value "bar2" at timestamp 4
print(kv.get("foo", 1))   # Output: "bar" (exact match for timestamp 1)
print(kv.get("foo", 3))   # Output: "bar" (closest timestamp <= 3 is 1)
print(kv.get("foo", 4))   # Output: "bar2" (exact match for timestamp 4)
print(kv.get("foo", 5))   # Output: "bar2" (closest timestamp <= 5 is 4)

Output:

bar
bar
bar2
bar2

Summary

By implementing a manual binary search, we achieve the same functionality as using bisect.bisect_right. The binary search helps us efficiently find the closest timestamp less than or equal to the target timestamp. This approach ensures that we can handle large datasets and perform fast lookups, similar to the behavior expected from the bisect module.

This manual binary search solution avoids external library dependencies and provides the same efficiency as using built-in methods like bisect_right.