981. Time Based Key-Value Store

Problem Link

We can store and retrieve standard key–value pairs in a hashmap in \(O(1)\). However, this problem requires searching for a given \(key\) and \(timestamp\), the value stored at the largest timestamp \(timestampPrev \le timestamp\).

The \(key\) lookup can still be done in \(O(1)\) using a hashmap. Since timestamps for each \(key\) are monotonically increasing, we can store the corresponding values (along with timestamps) in an array. This allows us to use binary search to find the required value in \(O(logn)\).

Using the standard binary search template, we find the minimum \(index\) such that \(timestamp \lt arr[index]\). The answer is then at \(index−1\), since we want the largest timestamp that is less than or equal to the given \(timestamp\).

Runtime Complexity

Time: \(O(1)\) for Set and \(O(logn)\) for Get

Space:\(O(mn)\), where \(m\) is the number of keys and \(n\) is the average number of values per key

PythonGo

class TimeMap:

    def __init__(self):
        self.data = defaultdict(list)


    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append((value, timestamp))

    def get(self, key: str, timestamp: int) -> str:
        items = self.data[key]
        if not items: return ""
        left, right = 0, len(items)
        while left < right:
            mid = left + (right-left)//2
            if timestamp < items[mid][1]:
                right = mid
            else:
                left = mid + 1
        return items[left - 1][0] if left > 0 else ""

type Datapoint struct {
    value     string
    timestamp int
}

type TimeMap struct {
    data map[string][]Datapoint
}

func Constructor2() TimeMap {
    return TimeMap{
        data: make(map[string][]Datapoint),
    }
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
    this.data[key] = append(this.data[key], Datapoint{
        value:     value,
        timestamp: timestamp,
    })
}

func (this *TimeMap) Get(key string, timestamp int) string {
    items, ok := this.data[key]
    if !ok {
        return ""
    }
    left, right := 0, len(items)
    var mid int
    for left < right {
        mid = left + (right-left)/2
        if timestamp < items[mid].timestamp {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if left > 0 {
        return items[left-1].value
    }
    return ""
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */

---