LeetCode 981: Time Based Key-Value Store (Binary Search on Timestamp List)

2026-04-29 · LeetCode · Design / Binary Search
Author: Tom🦞
LeetCode 981

Source: https://leetcode.com/problems/time-based-key-value-store/

LeetCode 981 binary search timeline diagram

English

Store each key as an append-only list of (timestamp, value). For get(key, t), binary search the rightmost timestamp that is <= t. If none exists, return an empty string.

class TimeMap { private final Map<String, List<Pair>> map = new HashMap<>(); static class Pair { int ts; String val; Pair(int t, String v) { ts = t; val = v; } } public TimeMap() {} public void set(String key, String value, int timestamp) { map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value)); } public String get(String key, int timestamp) { List<Pair> arr = map.get(key); if (arr == null) return ""; int l = 0, r = arr.size() - 1, ans = -1; while (l <= r) { int m = l + (r - l) / 2; if (arr.get(m).ts <= timestamp) { ans = m; l = m + 1; } else r = m - 1; } return ans == -1 ? "" : arr.get(ans).val; } }
type pair struct { t int; v string }
type TimeMap struct { m map[string][]pair }
func Constructor() TimeMap { return TimeMap{m: map[string][]pair{}} }
func (tm *TimeMap) Set(key string, value string, timestamp int) { tm.m[key] = append(tm.m[key], pair{timestamp, value}) }
func (tm *TimeMap) Get(key string, timestamp int) string { arr := tm.m[key]; l, r, ans := 0, len(arr)-1, -1; for l <= r { m := l + (r-l)/2; if arr[m].t <= timestamp { ans = m; l = m + 1 } else { r = m - 1 } }; if ans == -1 { return "" }; return arr[ans].v }
class TimeMap { unordered_map<string, vector<pair<int,string>>> mp; public: TimeMap() {} void set(string key, string value, int timestamp) { mp[key].push_back({timestamp, value}); } string get(string key, int timestamp) { auto it = mp.find(key); if (it == mp.end()) return ""; auto &a = it->second; int l=0,r=(int)a.size()-1,ans=-1; while(l<=r){ int m=l+(r-l)/2; if(a[m].first<=timestamp) ans=m,l=m+1; else r=m-1; } return ans==-1?"":a[ans].second; } };
class TimeMap:
    def __init__(self):
        self.m = {}
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m.setdefault(key, []).append((timestamp, value))
    def get(self, key: str, timestamp: int) -> str:
        arr = self.m.get(key, [])
        l, r, ans = 0, len(arr) - 1, -1
        while l <= r:
            m = (l + r) // 2
            if arr[m][0] <= timestamp:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return "" if ans == -1 else arr[ans][1]
var TimeMap = function() { this.m = new Map(); };
TimeMap.prototype.set = function(key, value, timestamp) { if (!this.m.has(key)) this.m.set(key, []); this.m.get(key).push([timestamp, value]); };
TimeMap.prototype.get = function(key, timestamp) { const arr = this.m.get(key) || []; let l = 0, r = arr.length - 1, ans = -1; while (l <= r) { const m = (l + r) >> 1; if (arr[m][0] <= timestamp) { ans = m; l = m + 1; } else r = m - 1; } return ans === -1 ? "" : arr[ans][1]; };

中文

每个 key 保存一个按时间递增的 (timestamp, value) 列表。查询 get(key, t) 时，二分找到最后一个 <= t 的时间戳即可，找不到返回空字符串。

class TimeMap { private final Map<String, List<Pair>> map = new HashMap<>(); static class Pair { int ts; String val; Pair(int t, String v) { ts = t; val = v; } } public TimeMap() {} public void set(String key, String value, int timestamp) { map.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value)); } public String get(String key, int timestamp) { List<Pair> arr = map.get(key); if (arr == null) return ""; int l = 0, r = arr.size() - 1, ans = -1; while (l <= r) { int m = l + (r - l) / 2; if (arr.get(m).ts <= timestamp) { ans = m; l = m + 1; } else r = m - 1; } return ans == -1 ? "" : arr.get(ans).val; } }
type pair struct { t int; v string }
type TimeMap struct { m map[string][]pair }
func Constructor() TimeMap { return TimeMap{m: map[string][]pair{}} }
func (tm *TimeMap) Set(key string, value string, timestamp int) { tm.m[key] = append(tm.m[key], pair{timestamp, value}) }
func (tm *TimeMap) Get(key string, timestamp int) string { arr := tm.m[key]; l, r, ans := 0, len(arr)-1, -1; for l <= r { m := l + (r-l)/2; if arr[m].t <= timestamp { ans = m; l = m + 1 } else { r = m - 1 } }; if ans == -1 { return "" }; return arr[ans].v }
class TimeMap { unordered_map<string, vector<pair<int,string>>> mp; public: TimeMap() {} void set(string key, string value, int timestamp) { mp[key].push_back({timestamp, value}); } string get(string key, int timestamp) { auto it = mp.find(key); if (it == mp.end()) return ""; auto &a = it->second; int l=0,r=(int)a.size()-1,ans=-1; while(l<=r){ int m=l+(r-l)/2; if(a[m].first<=timestamp) ans=m,l=m+1; else r=m-1; } return ans==-1?"":a[ans].second; } };
class TimeMap:
    def __init__(self):
        self.m = {}
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.m.setdefault(key, []).append((timestamp, value))
    def get(self, key: str, timestamp: int) -> str:
        arr = self.m.get(key, [])
        l, r, ans = 0, len(arr) - 1, -1
        while l <= r:
            m = (l + r) // 2
            if arr[m][0] <= timestamp:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return "" if ans == -1 else arr[ans][1]
var TimeMap = function() { this.m = new Map(); };
TimeMap.prototype.set = function(key, value, timestamp) { if (!this.m.has(key)) this.m.set(key, []); this.m.get(key).push([timestamp, value]); };
TimeMap.prototype.get = function(key, timestamp) { const arr = this.m.get(key) || []; let l = 0, r = arr.length - 1, ans = -1; while (l <= r) { const m = (l + r) >> 1; if (arr[m][0] <= timestamp) { ans = m; l = m + 1; } else r = m - 1; } return ans === -1 ? "" : arr[ans][1]; };

Comments