981. Time Based Key-Value Store (Medium)

Problem

Design a time-based key-value store:

• set(key, value, timestamp), store the key with the value at the given timestamp.
• get(key, timestamp), return the value associated with the key whose timestamp is the largest ≤ the query timestamp; if no such record exists, return "".

All set calls for a given key use strictly increasing timestamps.

Example

store.set("foo", "bar", 1)
store.get("foo", 1)    // "bar"
store.get("foo", 3)    // "bar"
store.set("foo", "bar2", 4)
store.get("foo", 4)    // "bar2"
store.get("foo", 5)    // "bar2"

LeetCode 981 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, linear scan per get

Per key, keep a list of (timestamp, value) entries. On get, scan linearly to find the largest timestamp ≤ query.

Python

from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.data = defaultdict(list)          # L1: O(1) init

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

    def get(self, key: str, timestamp: int) -> str:
        best = ""
        for ts, v in self.data[key]:           # L3: scan all entries for key, O(n)
            if ts <= timestamp:                # L4: O(1) compare
                best = v
            else:
                break                          # L5: early exit (timestamps sorted)
        return best

TypeScript

class TimeMap {
    private data: Map<string, [number, string][]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.data.has(key)) this.data.set(key, []);
        this.data.get(key)!.push([timestamp, value]);  // L2: O(1) amortized
    }

    get(key: string, timestamp: number): string {
        const entries = this.data.get(key) ?? [];
        let best = '';
        for (const [ts, v] of entries) {    // L3: scan all entries, O(n)
            if (ts <= timestamp) best = v;  // L4: O(1) compare
            else break;                     // L5: early exit (sorted)
        }
        return best;
    }
}

Go

type TimeMap struct {
    data map[string][][2]interface{}           // L1: O(1) init
}

func NewTimeMap() *TimeMap {
    return &TimeMap{data: make(map[string][][2]interface{})}
}

func (t *TimeMap) Set(key, value string, timestamp int) {
    t.data[key] = append(t.data[key], [2]interface{}{timestamp, value})  // L2: O(1) amortized
}

func (t *TimeMap) Get(key string, timestamp int) string {
    best := ""
    for _, e := range t.data[key] {                // L3: scan all entries, O(n)
        if e[0].(int) <= timestamp {               // L4: O(1) compare
            best = e[1].(string)
        } else {
            break                                  // L5: early exit (timestamps sorted)
        }
    }
    return best
}

Swift

private struct TimeMapEntry {
    let timestamp: Int
    let value: String
}

final class TimeMap {
    private var values: [String: [TimeMapEntry]] = [:]

    init() {}

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        values[key, default: []].append(TimeMapEntry(timestamp: timestamp, value: value))
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        guard let entries = values[key] else { return "" }
        for entry in entries.reversed() where entry.timestamp <= timestamp {
            return entry.value
        }
        return ""
    }
}

Where the time goes, line by line

Variables: n = number of set() calls for the queried key.

Line	Per-call cost	Times executed	Contribution
L2 (set append)	$O(1)$ amortized	1 per set call	$O(1)$ per set
L3/L4 (get scan)	$O(1)$	up to n	$O(n)$ per get ← dominates

set is $O(1)$; get scans entries until it finds a timestamp exceeding the query. With strictly increasing timestamps, the early break at L5 helps in the average case but not the worst case.

Complexity

• set: $O(1)$.
• get: $O(n)$ where n is entries for that key.
• Space: $O(n)$.

Approach 2: Binary search per get (manual implementation)

Since timestamps are strictly increasing per key, per-key lists are sorted. Binary-search them.

Python

from collections import defaultdict

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

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

    def get(self, key: str, timestamp: int) -> str:
        entries = self.data[key]
        lo, hi = 0, len(entries) - 1                # L2: O(1)
        result = ""
        while lo <= hi:                              # L3: binary search, O(log n) steps
            mid = (lo + hi) // 2                    # L4: O(1) midpoint
            if entries[mid][0] <= timestamp:         # L5: O(1) compare timestamp
                result = entries[mid][1]             # L6: O(1) record candidate
                lo = mid + 1                         # L7: O(1) look for larger ts
            else:
                hi = mid - 1                        # L8: O(1) too late, go earlier
        return result

TypeScript

class TimeMap {
    private data: Map<string, [number, string][]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.data.has(key)) this.data.set(key, []);
        this.data.get(key)!.push([timestamp, value]);    // L1: O(1) amortized
    }

    get(key: string, timestamp: number): string {
        const entries = this.data.get(key) ?? [];
        let lo = 0, hi = entries.length - 1;             // L2: O(1)
        let result = '';
        while (lo <= hi) {                               // L3: binary search, O(log n) steps
            const mid = (lo + hi) >> 1;                  // L4: O(1) midpoint
            if (entries[mid][0] <= timestamp) {          // L5: O(1) compare timestamp
                result = entries[mid][1];                // L6: O(1) record candidate
                lo = mid + 1;                            // L7: O(1) look for larger ts
            } else {
                hi = mid - 1;                            // L8: O(1) too late, go earlier
            }
        }
        return result;
    }
}

Go

type entry struct {
    timestamp int
    value     string
}

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

func NewTimeMap() *TimeMap {
    return &TimeMap{data: make(map[string][]entry)}
}

func (t *TimeMap) Set(key, value string, timestamp int) {
    t.data[key] = append(t.data[key], entry{timestamp, value})  // L1: O(1) amortized
}

func (t *TimeMap) Get(key string, timestamp int) string {
    entries := t.data[key]
    lo, hi := 0, len(entries)-1                // L2: O(1)
    result := ""
    for lo <= hi {                             // L3: binary search, O(log n) steps
        mid := (lo + hi) / 2                  // L4: O(1) midpoint
        if entries[mid].timestamp <= timestamp { // L5: O(1) compare timestamp
            result = entries[mid].value        // L6: O(1) record candidate
            lo = mid + 1                       // L7: O(1) look for larger ts
        } else {
            hi = mid - 1                       // L8: O(1) too late, go earlier
        }
    }
    return result
}

Swift

private struct TimeMapEntry {
    let timestamp: Int
    let value: String
}

final class TimeMap {
    private var values: [String: [TimeMapEntry]] = [:]

    init() {}

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        values[key, default: []].append(TimeMapEntry(timestamp: timestamp, value: value))
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        guard let entries = values[key] else { return "" }
        var low = 0
        var high = entries.count - 1
        var result = ""
        while low <= high {
            let middle = low + (high - low) / 2
            if entries[middle].timestamp <= timestamp {
                result = entries[middle].value
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = number of set() calls for the queried key.

Line	Per-call cost	Times executed	Contribution
L1 (set append)	$O(1)$ amortized	1 per set	$O(1)$ per set
L2 (init bounds)	$O(1)$	1 per get	$O(1)$
L3-L8 (binary search loop)	$O(1)$	log n	$O(log n)$ per get ← dominates

Since timestamps for each key are strictly increasing (guaranteed by the problem), the per-key list is sorted, enabling binary search. We track result as we go right, keeping the last valid timestamp found.

Complexity

• set: $O(1)$.
• get: $O(log n)$, driven by L3 (binary search over n sorted entries).
• Space: $O(n)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: bisect for clean per-key binary search (optimal, idiomatic)

Use Python’s bisect with parallel timestamps and values arrays per key.

Python

from collections import defaultdict
from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.timestamps = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.timestamps[key].append(timestamp)   # L1: O(1) amortized
        self.values[key].append(value)           # L2: O(1) amortized

    def get(self, key: str, timestamp: int) -> str:
        ts = self.timestamps[key]
        i = bisect_right(ts, timestamp) - 1      # L3: O(log n) binary search
        if i < 0:                                # L4: O(1)
            return ""
        return self.values[key][i]               # L5: O(1) index lookup

TypeScript

class TimeMap {
    private timestamps: Map<string, number[]> = new Map();
    private values: Map<string, string[]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.timestamps.has(key)) {
            this.timestamps.set(key, []);
            this.values.set(key, []);
        }
        this.timestamps.get(key)!.push(timestamp);   // L1: O(1) amortized
        this.values.get(key)!.push(value);           // L2: O(1) amortized
    }

    get(key: string, timestamp: number): string {
        const ts = this.timestamps.get(key) ?? [];
        // bisect_right equivalent: find insertion point for timestamp
        let lo = 0, hi = ts.length;
        while (lo < hi) {                            // L3: O(log n) binary search
            const mid = (lo + hi) >> 1;
            if (ts[mid] <= timestamp) lo = mid + 1;
            else hi = mid;
        }
        const i = lo - 1;                            // L4: rightmost index ≤ timestamp
        if (i < 0) return '';                        // L5: no entry before query
        return this.values.get(key)![i];             // L6: O(1) index lookup
    }
}

Go

type TimeMap struct {
    timestamps map[string][]int
    values     map[string][]string
}

func NewTimeMap() *TimeMap {
    return &TimeMap{
        timestamps: make(map[string][]int),
        values:     make(map[string][]string),
    }
}

func (t *TimeMap) Set(key, value string, timestamp int) {
    t.timestamps[key] = append(t.timestamps[key], timestamp)  // L1: O(1) amortized
    t.values[key] = append(t.values[key], value)              // L2: O(1) amortized
}

func (t *TimeMap) Get(key string, timestamp int) string {
    ts := t.timestamps[key]
    // bisect_right equivalent
    lo, hi := 0, len(ts)
    for lo < hi {                          // L3: O(log n) binary search
        mid := (lo + hi) / 2
        if ts[mid] <= timestamp {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    i := lo - 1                           // L4: rightmost index <= timestamp
    if i < 0 { return "" }               // L5: no entry before query
    return t.values[key][i]              // L6: O(1) index lookup
}

Swift

private struct TimeMapEntry {
    let timestamp: Int
    let value: String
}

final class TimeMap {
    private var values: [String: [TimeMapEntry]] = [:]

    init() {}

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        values[key, default: []].append(TimeMapEntry(timestamp: timestamp, value: value))
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        guard let entries = values[key] else { return "" }
        let insertionIndex = upperBound(entries, timestamp: timestamp)
        guard insertionIndex > 0 else { return "" }
        return entries[insertionIndex - 1].value
    }

    private func upperBound(_ entries: [TimeMapEntry], timestamp: Int) -> Int {
        var low = 0
        var high = entries.count
        while low < high {
            let middle = low + (high - low) / 2
            if entries[middle].timestamp <= timestamp {
                low = middle + 1
            } else {
                high = middle
            }
        }
        return low
    }
}

Where the time goes, line by line

Variables: n = number of set() calls for the queried key.

Line	Per-call cost	Times executed	Contribution
L1/L2 (set appends)	$O(1)$ amortized	1 per set	$O(1)$ per set
L3 (bisect_right)	$O(log n)$	1 per get	$O(log n)$ per get ← dominates
L4/L5 (bounds check + index)	$O(1)$	1 per get	$O(1)$

bisect_right(ts, timestamp) returns the insertion point for timestamp in the sorted ts list. Subtracting 1 gives the rightmost entry with timestamp ≤ the query. If i < 0, no entry exists for that key at or before the query.

Complexity

• set: $O(1)$ amortized, driven by L1/L2 (list appends).
• get: $O(log n)$, driven by L3 (bisect_right over n sorted timestamps).
• Space: $O(n)$.

bisect_right(ts, timestamp) - 1 returns the largest index whose timestamp is ≤ timestamp.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

The Swift implementation stores small TimeMapEntry values inside dictionary-owned arrays. values[key, default: []].append(...) mutates the selected array through the dictionary while copy-on-write preserves value semantics. Swift has no standard-library bisect, so Approach 3 packages the same upper-bound invariant into a reusable helper.

Summary

Approach	set	get	Space
Linear scan	$O(1)$	$O(n)$	$O(n)$
Manual binary search	$O(1)$	$O(log n)$	$O(n)$
bisect_right	$O(1)$	$O(log n)$	$O(n)$

The bisect version is idiomatic Python; the manual binary search is what you’d write in languages without a bisect-equivalent (Java: Collections.binarySearch; C++: upper_bound).

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_981.py and run.
# Uses the optimal Approach 3 implementation.

from collections import defaultdict
from bisect import bisect_right

class TimeMap:
    def __init__(self):
        self.timestamps = defaultdict(list)
        self.values = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        ts = self.timestamps[key]
        i = bisect_right(ts, timestamp) - 1
        if i < 0:
            return ""
        return self.values[key][i]

def _run_tests():
    store = TimeMap()
    store.set("foo", "bar", 1)
    assert store.get("foo", 1) == "bar"
    assert store.get("foo", 3) == "bar"     # no entry at 3, returns closest before
    store.set("foo", "bar2", 4)
    assert store.get("foo", 4) == "bar2"
    assert store.get("foo", 5) == "bar2"
    assert store.get("foo", 0) == ""        # before any entry
    assert store.get("missing", 1) == ""    # key never set
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TimeMap {
    private timestamps: Map<string, number[]> = new Map();
    private values: Map<string, string[]> = new Map();

    set(key: string, value: string, timestamp: number): void {
        if (!this.timestamps.has(key)) {
            this.timestamps.set(key, []);
            this.values.set(key, []);
        }
        this.timestamps.get(key)!.push(timestamp);
        this.values.get(key)!.push(value);
    }

    get(key: string, timestamp: number): string {
        const ts = this.timestamps.get(key) ?? [];
        let lo = 0, hi = ts.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (ts[mid] <= timestamp) lo = mid + 1;
            else hi = mid;
        }
        const i = lo - 1;
        if (i < 0) return '';
        return this.values.get(key)![i];
    }
}

const store = new TimeMap();
store.set("foo", "bar", 1);
console.assert(store.get("foo", 1) === "bar");
console.assert(store.get("foo", 3) === "bar");     // no entry at 3, returns closest before
store.set("foo", "bar2", 4);
console.assert(store.get("foo", 4) === "bar2");
console.assert(store.get("foo", 5) === "bar2");
console.assert(store.get("foo", 0) === "");        // before any entry
console.assert(store.get("missing", 1) === "");    // key never set
console.log("all tests pass");

Go

package main

import "fmt"

type TimeMap struct {
    timestamps map[string][]int
    values     map[string][]string
}

func NewTimeMap() *TimeMap {
    return &TimeMap{
        timestamps: make(map[string][]int),
        values:     make(map[string][]string),
    }
}

func (t *TimeMap) Set(key, value string, timestamp int) {
    t.timestamps[key] = append(t.timestamps[key], timestamp)
    t.values[key] = append(t.values[key], value)
}

func (t *TimeMap) Get(key string, timestamp int) string {
    ts := t.timestamps[key]
    lo, hi := 0, len(ts)
    for lo < hi {
        mid := (lo + hi) / 2
        if ts[mid] <= timestamp {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    i := lo - 1
    if i < 0 { return "" }
    return t.values[key][i]
}

func main() {
    store := NewTimeMap()
    store.Set("foo", "bar", 1)
    if store.Get("foo", 1) != "bar"  { panic("test 1") }
    if store.Get("foo", 3) != "bar"  { panic("test 2") } // no entry at 3, returns closest before
    store.Set("foo", "bar2", 4)
    if store.Get("foo", 4) != "bar2" { panic("test 3") }
    if store.Get("foo", 5) != "bar2" { panic("test 4") }
    if store.Get("foo", 0) != ""     { panic("test 5") } // before any entry
    if store.Get("missing", 1) != "" { panic("test 6") } // key never set
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, per-key sorted timestamp list
• Hash Tables, outer key → list mapping

Related concepts

• Binary Search, monotonic search tactics for cutting a sorted or ordered search space in half until one answer remains.
• Modified Binary Search, binary-search variants for rotated arrays, peak finding, and data where the ordering is present but disguised.