981. Time Based Key Value Store - Explanation

Description

Implement a time-based key-value data structure that supports:

Storing multiple values for the same key at specified time stamps
Retrieving the key's value at a specified timestamp

Implement the TimeMap class:

TimeMap() Initializes the object.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns the most recent value of key if set was previously called on it and the most recent timestamp for that key prev_timestamp is less than or equal to the given timestamp (prev_timestamp <= timestamp). If there are no values, it returns "".

Note: For all calls to set, the timestamps are in strictly increasing order.

Example 1:

Input:
["TimeMap", "set", ["alice", "happy", 1], "get", ["alice", 1], "get", ["alice", 2], "set", ["alice", "sad", 3], "get", ["alice", 3]]

Output:
[null, null, "happy", "happy", null, "sad"]

Explanation:
TimeMap timeMap = new TimeMap();
timeMap.set("alice", "happy", 1);  // store the key "alice" and value "happy" along with timestamp = 1.
timeMap.get("alice", 1);           // return "happy"
timeMap.get("alice", 2);           // return "happy", there is no value stored for timestamp 2, thus we return the value at timestamp 1.
timeMap.set("alice", "sad", 3);    // store the key "alice" and value "sad" along with timestamp = 3.
timeMap.get("alice", 3);           // return "sad"

Constraints:

1 <= key.length, value.length <= 100
key and value only include lowercase English letters and digits.
1 <= timestamp <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(1) time for set(), O(logn) time for get(), and O(m * n) space, where n is the total number of values associated with a key, and m is the total number of keys.

Hint 1

Can you think of a data structure that is useful for storing key-value pairs? Perhaps a hash-based data structure where we not only store unique elements but also associate additional information with each element?

Hint 2

We store key-value pairs in a hash map. In this case, we store the keys as usual, but instead of a single value, we store a list of values, each paired with its corresponding timestamp. This allows us to implement the set() method in O(1). How can you leverage this hash map to implement the get() method?

Hint 3

A brute force solution would involve linearly going through every value associated with the key and returning the most recent value with a timestamp less than or equal to the given timestamp. This approach has a time complexity of O(n) for each get() call. Can you think of a better way? Since the timestamps in the value list are sorted in ascending order by default, maybe an efficient searching algorithm could help.

Hint 4

We can use binary search because the timestamps in the values list are sorted in ascending order. This makes it straightforward to find the value with the most recent timestamp that is less than or equal to the given timestamp.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash maps/dictionaries - Storing key-value pairs with efficient lookup
Binary search - Finding the largest timestamp less than or equal to the query in O(log n)
Sorted data structures - Maintaining timestamps in sorted order for efficient searching

1. Brute Force

Intuition

We want to store values for a key along with timestamps, and when someone asks for a value at a given time, we must return the latest value set at or before that timestamp.

The brute-force idea is:
store everything as-is, and while retrieving, look through all timestamps for that key and pick the best match.
It's easy to implement, but slow because we scan all timestamps every time we call get().

Algorithm

Use a dictionary to map each key to another dictionary of timestamps → list of values.
When setting a value:
- Insert the value under the corresponding timestamp.
When getting a value:
- If the key does not exist, return an empty string.
- Otherwise, loop through all timestamps for that key.
- Track the largest timestamp ≤ given timestamp.
- Return the value stored at that timestamp.
If no such timestamp exists, return an empty string.

class TimeMap:

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

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = {}
        if timestamp not in self.keyStore[key]:
            self.keyStore[key][timestamp] = []
        self.keyStore[key][timestamp].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.keyStore:
            return ""
        seen = 0

        for time in self.keyStore[key]:
            if time <= timestamp:
                seen = max(seen, time)
        return "" if seen == 0 else self.keyStore[key][seen][-1]

public class TimeMap {
    private Map<String, Map<Integer, List<String>>> keyStore;

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

    public void set(String key, String value, int timestamp) {
        if (!keyStore.containsKey(key)) {
            keyStore.put(key, new HashMap<>());
        }
        if (!keyStore.get(key).containsKey(timestamp)) {
            keyStore.get(key).put(timestamp, new ArrayList<>());
        }
        keyStore.get(key).get(timestamp).add(value);
    }

    public String get(String key, int timestamp) {
        if (!keyStore.containsKey(key)) {
            return "";
        }
        int seen = 0;

        for (int time : keyStore.get(key).keySet()) {
            if (time <= timestamp) {
                seen = Math.max(seen, time);
            }
        }
        if (seen == 0) return "";
        int back = keyStore.get(key).get(seen).size() - 1;
        return keyStore.get(key).get(seen).get(back);
    }
}

class TimeMap {
public:
    unordered_map<string, unordered_map<int, vector<string>>> keyStore;
    TimeMap() {}

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

    string get(string key, int timestamp) {
        if (keyStore.find(key) == keyStore.end()) {
            return "";
        }
        int seen = 0;
        for (const auto& [time, _] : keyStore[key]) {
            if (time <= timestamp) {
                seen = max(seen, time);
            }
        }
        return seen == 0 ? "" : keyStore[key][seen].back();
    }
};

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

    /**
     * @param {string} key
     * @param {string} value
     * @param {number} timestamp
     * @return {void}
     */
    set(key, value, timestamp) {
        if (!this.keyStore.has(key)) {
            this.keyStore.set(key, new Map());
        }
        if (!this.keyStore.get(key).has(timestamp)) {
            this.keyStore.get(key).set(timestamp, []);
        }
        this.keyStore.get(key).get(timestamp).push(value);
    }

    /**
     * @param {string} key
     * @param {number} timestamp
     * @return {string}
     */
    get(key, timestamp) {
        if (!this.keyStore.has(key)) {
            return '';
        }
        let seen = 0;

        for (let time of this.keyStore.get(key).keys()) {
            if (time <= timestamp) {
                seen = Math.max(seen, time);
            }
        }
        return seen === 0 ? '' : this.keyStore.get(key).get(seen).at(-1);
    }
}

public class TimeMap {
    private Dictionary<string, Dictionary<int, List<string>>> keyStore;

    public TimeMap() {
        keyStore = new Dictionary<string, Dictionary<int, List<string>>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!keyStore.ContainsKey(key)) {
            keyStore[key] = new Dictionary<int, List<string>>();
        }
        if (!keyStore[key].ContainsKey(timestamp)) {
            keyStore[key][timestamp] = new List<string>();
        }
        keyStore[key][timestamp].Add(value);
    }

    public string Get(string key, int timestamp) {
        if (!keyStore.ContainsKey(key)) {
            return "";
        }
        var timestamps = keyStore[key];
        int seen = 0;

        foreach (var time in timestamps.Keys) {
            if (time <= timestamp) {
                seen = time;
            }
        }
        return seen == 0 ? "" : timestamps[seen][^1];
    }
}

type TimeMap struct {
   keyStore map[string]map[int][]string
}

func Constructor() TimeMap {
   return TimeMap{
       keyStore: make(map[string]map[int][]string),
   }
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
   if _, exists := this.keyStore[key]; !exists {
       this.keyStore[key] = make(map[int][]string)
   }
   this.keyStore[key][timestamp] = append(this.keyStore[key][timestamp], value)
}

func (this *TimeMap) Get(key string, timestamp int) string {
   if _, exists := this.keyStore[key]; !exists {
       return ""
   }

   seen := 0
   for time := range this.keyStore[key] {
       if time <= timestamp {
           seen = max(seen, time)
       }
   }

   if seen == 0 {
       return ""
   }
   values := this.keyStore[key][seen]
   return values[len(values)-1]
}

func max(a, b int) int {
   if a > b {
       return a
   }
   return b
}

class TimeMap() {
    private val keyStore = HashMap<String, HashMap<Int, MutableList<String>>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!keyStore.containsKey(key)) {
            keyStore[key] = HashMap()
        }
        if (!keyStore[key]!!.containsKey(timestamp)) {
            keyStore[key]!![timestamp] = mutableListOf()
        }
        keyStore[key]!![timestamp]!!.add(value)
    }

    fun get(key: String, timestamp: Int): String {
        if (!keyStore.containsKey(key)) {
            return ""
        }

        var seen = 0
        for (time in keyStore[key]!!.keys) {
            if (time <= timestamp) {
                seen = maxOf(seen, time)
            }
        }

        if (seen == 0) {
            return ""
        }
        return keyStore[key]!![seen]!!.last()
    }
}

class TimeMap {
    private var keyStore: [String: [Int: [String]]]

    init() {
        self.keyStore = [:]
    }

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        if keyStore[key] == nil {
            keyStore[key] = [:]
        }
        if keyStore[key]![timestamp] == nil {
            keyStore[key]![timestamp] = []
        }
        keyStore[key]![timestamp]!.append(value)
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        guard let timeMap = keyStore[key] else {
            return ""
        }

        var seen = 0
        for time in timeMap.keys {
            if time <= timestamp {
                seen = max(seen, time)
            }
        }
        return seen == 0 ? "" : timeMap[seen]!.last!
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for $set()$ and $O(n)$ for $get()$ .
Space complexity: $O(m * n)$

Where $n$ is the total number of unique timestamps associated with a key and $m$ is the total number of keys.

2. Binary Search (Sorted Map)

Intuition

For each key, we store all its (timestamp, value) pairs in sorted order by timestamp.

When we call get(key, timestamp), we don’t want to scan everything.
Instead, we want to quickly find the largest timestamp ≤ given timestamp for that key.

Because the timestamps are sorted, we can use binary search to find this position in O(log n) time:

If we find an exact match, return its value.
Otherwise, return the value at the closest smaller timestamp.
If there is no smaller or equal timestamp, return "".

So the idea is:

Per key → keep timestamps sorted.
On get → binary search over those timestamps.

Algorithm

Maintain a map:
key -> sorted list of (timestamp, value) (or two parallel arrays: one for timestamps, one for values).
set(key, value, timestamp):
- Insert (timestamp, value) into the list for that key, keeping timestamps in sorted order.
- (If timestamps are always added in increasing order, you can just append.)
get(key, timestamp):
- If key does not exist, return "".
- Let times be the sorted list of timestamps for this key.
- Use binary search on times to find the rightmost index i such that times[i] ≤ timestamp.
- If such an index exists:
  - Return the value associated with times[i].
- Otherwise:
  - Return "" (no value was set at or before that time).

from sortedcontainers import SortedDict

class TimeMap:
    def __init__(self):
        self.m = defaultdict(SortedDict)

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.m:
            return ""

        timestamps = self.m[key]
        idx = timestamps.bisect_right(timestamp) - 1

        if idx >= 0:
            closest_time = timestamps.iloc[idx]
            return timestamps[closest_time]
        return ""

public class TimeMap {
    private Map<String, TreeMap<Integer, String>> m;

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

    public void set(String key, String value, int timestamp) {
        m.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!m.containsKey(key)) return "";
        TreeMap<Integer, String> timestamps = m.get(key);
        Map.Entry<Integer, String> entry = timestamps.floorEntry(timestamp);
        return entry == null ? "" : entry.getValue();
    }
}

class TimeMap {
public:
    unordered_map<string, map<int, string>> m;

    TimeMap() {}

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

    string get(string key, int timestamp) {
        auto it = m[key].upper_bound(timestamp);
        return it == m[key].begin() ? "" : prev(it)->second;
    }
};

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

    /**
     * @param {string} key
     * @param {string} value
     * @param {number} timestamp
     * @return {void}
     */
    set(key, value, timestamp) {
        if (!this.keyStore.has(key)) {
            this.keyStore.set(key, []);
        }
        this.keyStore.get(key).push([timestamp, value]);
    }

    /**
     * @param {string} key
     * @param {number} timestamp
     * @return {string}
     */
    get(key, timestamp) {
        const values = this.keyStore.get(key) || [];
        let left = 0;
        let right = values.length - 1;
        let result = '';

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (values[mid][0] <= timestamp) {
                result = values[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

public class TimeMap {
    private Dictionary<string, SortedList<int, string>> m;

    public TimeMap() {
        m = new Dictionary<string, SortedList<int, string>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!m.ContainsKey(key)) {
            m[key] = new SortedList<int, string>();
        }
        m[key][timestamp] = value;
    }

    public string Get(string key, int timestamp) {
        if (!m.ContainsKey(key)) return "";
        var timestamps = m[key];
        int left = 0;
        int right = timestamps.Count - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (timestamps.Keys[mid] == timestamp) {
                return timestamps.Values[mid];
            } else if (timestamps.Keys[mid] < timestamp) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (right >= 0) {
            return timestamps.Values[right];
        }
        return "";
    }
}

type TimeMap struct {
   m map[string][]pair
}

type pair struct {
   timestamp int
   value string
}

func Constructor() TimeMap {
   return TimeMap{
       m: make(map[string][]pair),
   }
}

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

func (this *TimeMap) Get(key string, timestamp int) string {
   if _, exists := this.m[key]; !exists {
       return ""
   }

   pairs := this.m[key]
   idx := sort.Search(len(pairs), func(i int) bool {
       return pairs[i].timestamp > timestamp
   })

   if idx == 0 {
       return ""
   }
   return pairs[idx-1].value
}

class TimeMap() {
    private val m = HashMap<String, TreeMap<Int, String>>()

    fun set(key: String, value: String, timestamp: Int) {
        m.computeIfAbsent(key) { TreeMap() }[timestamp] = value
    }

    fun get(key: String, timestamp: Int): String {
        if (!m.containsKey(key)) return ""
        return m[key]!!.floorEntry(timestamp)?.value ?: ""
    }
}

Time & Space Complexity

Time complexity: $O(n)$ or $O(\log n)$ for $set()$ depending on the language and $O(\log n)$ for $get()$ .
Space complexity: $O(m * n)$

Where $n$ is the total number of values associated with a key and $m$ is the total number of keys.

3. Binary Search (Array)

Intuition

Each key stores its values in the order they were inserted, and timestamps are guaranteed to be increasing for each key.
This means we can keep a simple list of (value, timestamp) pairs for every key.

To answer a get(key, timestamp) query, we only need to find the latest timestamp that is ≤ the given timestamp.
Because timestamps are sorted, we can use binary search to quickly find this position instead of scanning everything.

This gives an efficient and clean approach:
store values in arrays, then binary-search timestamps when retrieving.

Algorithm

Use a dictionary:
- key → list of [value, timestamp]
- Timestamps for each key are stored in sorted order (because they arrive in increasing order).
set(key, value, timestamp):
- Append [value, timestamp] to the key’s list.
get(key, timestamp):
- If the key does not exist, return "".
- Let arr be the list of [value, timestamp] pairs.
- Perform binary search on timestamps to find the rightmost timestamp t ≤ timestamp.
- If found, return the corresponding value.
- If not found, return "".

class TimeMap:

    def __init__(self):
        self.keyStore = {}  # key : list of [val, timestamp]

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.keyStore:
            self.keyStore[key] = []
        self.keyStore[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        res, values = "", self.keyStore.get(key, [])
        l, r = 0, len(values) - 1
        while l <= r:
            m = (l + r) // 2
            if values[m][1] <= timestamp:
                res = values[m][0]
                l = m + 1
            else:
                r = m - 1
        return res

public class TimeMap {

    private Map<String, List<Pair<Integer, String>>> keyStore;

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

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

    public String get(String key, int timestamp) {
        List<Pair<Integer, String>> values = keyStore.getOrDefault(key, new ArrayList<>());
        int left = 0, right = values.size() - 1;
        String result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values.get(mid).getKey() <= timestamp) {
                result = values.get(mid).getValue();
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }

    private static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> keyStore;

public:
    TimeMap() {}

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

    string get(string key, int timestamp) {
        auto& values = keyStore[key];
        int left = 0, right = values.size() - 1;
        string result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values[mid].first <= timestamp) {
                result = values[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
};

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

    /**
     * @param {string} key
     * @param {string} value
     * @param {number} timestamp
     * @return {void}
     */
    set(key, value, timestamp) {
        if (!this.keyStore.has(key)) {
            this.keyStore.set(key, []);
        }
        this.keyStore.get(key).push([timestamp, value]);
    }

    /**
     * @param {string} key
     * @param {number} timestamp
     * @return {string}
     */
    get(key, timestamp) {
        const values = this.keyStore.get(key) || [];
        let left = 0;
        let right = values.length - 1;
        let result = '';

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (values[mid][0] <= timestamp) {
                result = values[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

public class TimeMap {

    private Dictionary<string, List<Tuple<int, string>>> keyStore;

    public TimeMap() {
        keyStore = new Dictionary<string, List<Tuple<int, string>>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!keyStore.ContainsKey(key)) {
            keyStore[key] = new List<Tuple<int, string>>();
        }
        keyStore[key].Add(Tuple.Create(timestamp, value));
    }

    public string Get(string key, int timestamp) {
        if (!keyStore.ContainsKey(key)) {
            return "";
        }

        var values = keyStore[key];
        int left = 0, right = values.Count - 1;
        string result = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (values[mid].Item1 <= timestamp) {
                result = values[mid].Item2;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

type TimeMap struct {
   m map[string][]pair
}

type pair struct {
   timestamp int
   value     string
}

func Constructor() TimeMap {
   return TimeMap{
       m: make(map[string][]pair),
   }
}

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

func (this *TimeMap) Get(key string, timestamp int) string {
   if _, exists := this.m[key]; !exists {
       return ""
   }

   pairs := this.m[key]
   l, r := 0, len(pairs)-1

   for l <= r {
       mid := (l + r) / 2
       if pairs[mid].timestamp <= timestamp {
           if mid == len(pairs)-1 || pairs[mid+1].timestamp > timestamp {
               return pairs[mid].value
           }
           l = mid + 1
       } else {
           r = mid - 1
       }
   }
   return ""
}

class TimeMap() {
    private val keyStore = HashMap<String, MutableList<Pair<String, Int>>>()

    fun set(key: String, value: String, timestamp: Int) {
        if (!keyStore.containsKey(key)) {
            keyStore[key] = mutableListOf()
        }
        keyStore[key]!!.add(Pair(value, timestamp))
    }

    fun get(key: String, timestamp: Int): String {
        var res = ""
        val values = keyStore[key] ?: return res
        var l = 0
        var r = values.size - 1

        while (l <= r) {
            val m = (l + r) / 2
            if (values[m].second <= timestamp) {
                res = values[m].first
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return res
    }
}

class TimeMap {
    private var keyStore: [String: [(String, Int)]]

    init() {
        self.keyStore = [:]
    }

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        if keyStore[key] == nil {
            keyStore[key] = []
        }
        keyStore[key]!.append((value, timestamp))
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        guard let values = keyStore[key] else {
            return ""
        }

        var res = ""
        var l = 0, r = values.count - 1

        while l <= r {
            let m = (l + r) / 2
            if values[m].1 <= timestamp {
                res = values[m].0
                l = m + 1
            } else {
                r = m - 1
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(1)$ for $set()$ and $O(\log n)$ for $get()$ .
Space complexity: $O(m * n)$

Where $n$ is the total number of values associated with a key and $m$ is the total number of keys.

Common Pitfalls

Using Exact Match Instead of Floor Search

A common mistake is searching for an exact timestamp match instead of finding the largest timestamp less than or equal to the query. Binary search should find the rightmost value satisfying timestamp <= query, not an exact match. If no exact match exists but earlier timestamps do, returning an empty string is incorrect.

Off-By-One Errors in Binary Search

Binary search boundaries are tricky. Using bisect_left instead of bisect_right, or not adjusting the index after the search, leads to returning values from timestamps greater than the query. Always verify your binary search returns the correct floor value by testing edge cases like querying before any set operation.

Returning Empty String When Key Exists But Timestamp Is Too Early

When a key exists but all stored timestamps are greater than the query timestamp, the correct behavior is to return an empty string. Some implementations incorrectly return the earliest stored value instead. Always check that your found index is valid (non-negative) before accessing the value.