LeetCode 981 · Binary Search

Time Based Key-Value Store, explained with a picture

A diary that answers “what was it at time t?”.

MediumBinary Search
▶ Watch it step by step

The problem

Design a key-value store that keeps history. set(key, value, time) stores a value at a time; get(key, time) returns the value set at the latest time that is ≤ the asked time, or "" if there is none. Times for set are increasing.

Input:  set mood happy 1, set mood calm 4, set mood sleepy 7, set mood hungry 9,
        get mood 5, get mood 9, get mood 0
Output: "calm", "hungry", ""

Picture it

Picture a diary for each key. Every set writes a new page stamped with the time. To answer “what was the mood at time 5?”, flip to the last page written at or before 5. Since pages are already in time order, we don’t flip through all of them: we binary search for the right page.

How to recognise it

  • You must design a class that stores a history of values per key and answers "what was it at time t?".
  • The question is "the latest entry at or before t": a last position where a condition holds, which is a boundary search.
  • set is called with increasing times, so appending to a list keeps each key's history sorted for free. No sorting step is needed.
  • Up to 2 × 10^5 calls, so scanning a key's whole history on every get is too slow.

Start with brute force

Store (time, value) pairs per key, as the shown code does, and let get scan the whole list, keeping the last value whose time is not after t.

from collections import defaultdict

class TimeMapBrute:
    def __init__(self):
        self.pages = defaultdict(list)
    def set(self, key, value, time):
        self.pages[key].append((time, value))
    def get(self, key, time):
        ans = ""
        for t, v in self.pages[key]:
            if t <= time:
                ans = v
        return ans

set is O(1), but get is O(k) for a key with k entries. With 10^5 sets on one key followed by 10^5 gets, that is about 10^10 steps.

From brute force to the idea

  1. Find the waste. The history is sorted by time, but the scan ignores that and reads every entry.
  2. Name the target. You want the last page whose time is at most time. Times at or before it form a prefix of the list, so there is one boundary to find.
  3. Binary search, remembering the best so far. Keep lo..hi inclusive. If pages[mid][0] <= time, this page is a valid answer, so record its value in ans, then look further right for a later one: lo = mid + 1. Otherwise the page is too late: hi = mid - 1.
  4. The last recorded value wins. Each time ans is updated, it is at a later valid position than before, so when the range empties ans holds the latest one.
  5. Nothing found means "". ans starts as "", which is exactly what the problem wants when every page is after time, or the key was never set.

This is the key idea: keep each key's pages in time order and binary search for the last page whose time is at most t.

The key idea

Store (time, value) lists per key in time order; get = binary search for the last time ≤ t. O(log n) per get.

Python solution

class TimeMap:
    def __init__(self):
        self.pages = defaultdict(list)       # key -> [(time, value)]
    def set(self, key, value, time):
        self.pages[key].append((time, value)) # times only increase
    def get(self, key, time):
        pages, ans = self.pages[key], ""
        lo, hi = 0, len(pages) - 1
        while lo <= hi:                       # last page with time <= t
            mid = (lo + hi) // 2
            if pages[mid][0] <= time:
                ans, lo = pages[mid][1], mid + 1
            else:
                hi = mid - 1
        return ans

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceset O(1); get O(k): scans all k entries of the keyO(total sets)
Binary search (shown code)set O(1) amortised; get O(log k)O(total sets)

Edge cases

  • Imports: the shown code needs from collections import defaultdict; without it, creating a TimeMap raises NameError.
  • The example: get("mood", 5) is "calm", get("mood", 9) is "hungry", get("mood", 0) is "".
  • Exact time match (get("mood", 4)): returns "calm", because the comparison is <=.
  • Time after the last set (get("mood", 100)): returns "hungry".
  • Unknown key: returns "", but self.pages[key] on a defaultdict creates an empty list for that key. Many gets for unknown keys therefore use memory. self.pages.get(key, []) avoids it.
  • The increasing-times promise: if set were called out of order, the list would not be sorted and the search could return wrong values. The shown code does not check.

Common mistakes

  • Using < instead of <=, which skips the entry set at exactly the asked time.
  • Returning pages[hi][1] after the loop without checking hi >= 0. When every time is too late, hi is −1 and Python quietly returns the last page.
  • Storing one dictionary per key of time -> value and looking up the exact time. That fails for any time between two sets.
  • Sorting the list inside get, which costs O(k log k) per call.
Your turn: everything in a time window

Add get_range(key, t1, t2) that returns, in time order, every value set for the key at a time between t1 and t2 inclusive. For the example, get_range("mood", 4, 8) is ["calm", "sleepy"]. Describe your approach, then write it if you like.

Compare with our answer

Find both ends of the window with two binary searches: the first time at or after t1, and the first time after t2. The values between those positions are the answer. Keeping times and values in two parallel lists lets Python's bisect module do the searches.

from bisect import bisect_left, bisect_right
from collections import defaultdict

class TimeLog:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)
    def set(self, key, value, time):
        self.times[key].append(time)
        self.values[key].append(value)
    def get_range(self, key, t1, t2):
        ts = self.times[key]
        i = bisect_left(ts, t1)          # first time >= t1
        j = bisect_right(ts, t2)         # first time > t2
        return self.values[key][i:j]

Time O(log k + r) for r returned values. If t1 > t2 the slice is empty.

A strong answer mentions: which side each search is biased to (left for t1, right for t2), why the slice end is exclusive, and the O(log k + r) cost.

Check what stuck

1. A stock service records each symbol's price whenever it changes, in time order, and must answer "what was the price at 14:03:27?". Which approach fits best?

2. Why does get record ans before moving lo = mid + 1, instead of returning at once?

3. A learner changes the test to if pages[mid][0] < time:. Using the example, which call now returns the wrong value?

Score 60% or more and the lesson is marked complete.