Difficulty: Medium · LeetCode 981

Problem

Design a key-value data structure that can store multiple values for the same key at different timestamps and retrieve key value at timestamp_prev <= timestamp.

Understanding the problem

Timestamps for a key are added in strictly increasing order, so timestamps per key are sorted.

Intuition

Binary search for the rightmost element whose timestamp $\le$ requested timestamp.

Approach

set(key, val, time): append (time, val) to list store[key].
get(key, target_time): binary search values = store[key].
While left <= right:
If values[mid][0] <= target_time: record answer = values[mid][1] and search right left = mid + 1.
Else: search left right = mid - 1.
Return answer.

Naive Solution — Brute Force

Store list of (timestamp, value) tuples and scan backward linearly on get().

Python

class TimeMap:

    def __init__(self):
        self.store = {}

    def set(self, key, value, timestamp):

        if key not in self.store:
            self.store[key] = []

        self.store[key].append(
            (timestamp, value)
        )

    def get(self, key, timestamp):

        if key not in self.store:
            return ""

        result = ""

        for time, value in reversed(
            self.store[key]
        ):
            if time <= timestamp:
                return value

        return result

C++

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end()) {
            return "";
        }

        const auto& values = it->second;

        for (int i = values.size() - 1; i >= 0; i--) {
            if (values[i].first <= timestamp) {
                return values[i].second;
            }
        }

        return "";
    }
};

Java

class TimeMap {
    private Map<String, List<Pair>> store;

    private static class Pair {
        int time;
        String value;

        Pair(int time, String value) {
            this.time = time;
            this.value = value;
        }
    }

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) {
            return "";
        }

        List<Pair> values = store.get(key);

        for (int i = values.size() - 1; i >= 0; i--) {
            if (values.get(i).time <= timestamp) {
                return values.get(i).value;
            }
        }

        return "";
    }
}

JavaScript

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, []);
        }

        this.store.get(key).push([timestamp, value]);
    }

    get(key, timestamp) {
        if (!this.store.has(key)) {
            return "";
        }

        const values = this.store.get(key);

        for (let i = values.length - 1; i >= 0; i--) {
            if (values[i][0] <= timestamp) {
                return values[i][1];
            }
        }

        return "";
    }
}

get: O(n), set: O(1) · Space: O(n)

Optimized Code (Python 3)

Python

class TimeMap:

    def __init__(self):
        self.store = {}

    def set(self, key, value, timestamp):

        if key not in self.store:
            self.store[key] = []

        self.store[key].append(
            (timestamp, value)
        )

    def get(self, key, timestamp):

        if key not in self.store:
            return ""

        values = self.store[key]

        left = 0
        right = len(values) - 1

        answer = ""

        while left <= right:

            mid = left + (right - left) // 2

            if values[mid][0] <= timestamp:
                answer = values[mid][1]
                left = mid + 1
            else:
                right = mid - 1

        return answer

C++

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;

public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end()) {
            return "";
        }

        const auto& values = it->second;

        int left = 0;
        int right = values.size() - 1;

        string answer = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (values[mid].first <= timestamp) {
                answer = values[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return answer;
    }
};

Java

class TimeMap {
    private Map<String, List<Pair>> store;

    private static class Pair {
        int time;
        String value;

        Pair(int time, String value) {
            this.time = time;
            this.value = value;
        }
    }

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) {
            return "";
        }

        List<Pair> values = store.get(key);

        int left = 0;
        int right = values.size() - 1;

        String answer = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (values.get(mid).time <= timestamp) {
                answer = values.get(mid).value;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return answer;
    }
}

JavaScript

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, []);
        }

        this.store.get(key).push([timestamp, value]);
    }

    get(key, timestamp) {
        if (!this.store.has(key)) {
            return "";
        }

        const values = this.store.get(key);

        let left = 0;
        let right = values.length - 1;

        let answer = "";

        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);

            if (values[mid][0] <= timestamp) {
                answer = values[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return answer;
    }
}

get: O(log n), set: O(1) · Space: O(n)

Takeaway

Pattern — Sorted timestamps → Rightmost valid binary search