LeetCode-981. Time Based Key-Value Store.

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.

Implement the `TimeMap`

class:

`TimeMap()`

Initializes the object of the data structure.`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 a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.

In the Java world, the way I would think about solving this problem is a 3-Dimensional Map. We not only need to keep a key-value pair, we also need to track it versus time.

The key does not change with time, but the value does. So we need to have a list of values for a given key at different timestamps.

This could be a very good application for a weather app. The key would be the city name, and the values would be the temperature on a given day.

Example:

```
set("berlin", "15", 1);
set("paris", "17", 1);
set("london", "9", 2);
set("paris", "19", 2);
get("berlin", 1); // get weather for Berlin @ 1 = {"15"}
set("paris", "12", 6);
get("paris", 3); // no value for Paris @ 3, closest is @ 2 ={"19"}
set("berlin", "17", 2);
set("london", "10", 4);
get("london", 10); // no value for London @ 10, closest is @ 4 ={"10"}
set("london", "3", 5);
```

According to the problem description, `get()`

should return “** a value such that set was called previously, with timestamp_prev <= timestamp**”, which is why we returned the value @ 2 for Paris and @ 4 for London.

We will create a Map whose key is city name and its value is a List containing the pair of value & timestamp. With each `get()`

call, we loop through all the values for the given key, until we get the one at the closest timestamp.

`Map<String, List<Pair<Integer, String>>> lookup;`

With every `get()`

call, we will go through all the timestamps, so the time complexity will be O(n) where `n`

is the number of values for a given key.

However, if we sort those values based on their timestamps, we could easily perform binary search, so the complexity becomes O(`log(n)`

).

The preferred data structure in Java for binary search is the `TreeMap`

. So our `lookup`

will become:

`Map<String, TreeMap<Integer, String>> lookup;`

`set()`

is called?- Get the sorted list of values for a given key with their corresponding timestamps
- Add a new entry to the sorted list
- Update the
`lookup`

table with the new data

`get()`

is called?- Get the sorted list of values for a given key if it exists in the
`lookup`

table - Perform a binary search to find the closest timestamp
- Return the value at the closest timestamp
- If no value is found, return an empty string

- Time complexity:
O(1) to get the key from the map (in our example, city), then O(
`log(n)`

) to get the value at a given timestamp.

So overall time complexity is O(`log(n)`

).

- Space complexity: We are not using any “EXTRA” space. The data is stored in the same object that we query, so the space complexity is O(1).

```
class TimeMap {
Map<String, TreeMap<Integer, String>> lookup;
public TimeMap() {
lookup = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
TreeMap<Integer, String> sortedValuesForKey = lookup.getOrDefault(key, new TreeMap<>());
sortedValuesForKey.put(timestamp, value);
lookup.put(key, sortedValuesForKey);
}
public String get(String key, int timestamp) {
if(!lookup.containsKey(key)) return "";
TreeMap<Integer, String> sortedValuesForKey = lookup.get(key);
Integer closestTimestamp = sortedValuesForKey.floorKey(timestamp);
if(closestTimestamp == null) return "";
return sortedValuesForKey.getOrDefault(closestTimestamp, "");
}
}
```

`sortedValuesForKey.floorKey(timestamp);`

returns the greatest key less than or equal to the given key, or null if there is no such key; this is the main binary search operation in the code, and it is exactly what we need to find the closest timestamp.

I hope you enjoyed this post.

If you have any questions, please feel free to reach out via LinkedIn Linkedin.com/omaryaya