Time Based Key Value Store - Leetcode Solution

Problem: 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 value of the key at a certain time.

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 the key key and the timestamp timestamp. If there are multiple such values, it returns the one with the largest timestamp that is less than or equal to timestamp. If there are no values, it returns "".

Example 1:

Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1 timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to "foo" at timestamp 3 and the closest previous value is at timestamp 1 timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4 timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

Constraints:

1 <= key.length, value.length <= 100 1 <= timestamp <= 10^7 All the strings of key and value and the timestamp will be lowercase English letters and integers in the range [a-z, 0-9].

Solution:

The approach to solve this problem is to create a hashmap where each key will point to a list of pairs where each pair will have two values – value and timestamp.

During set operation, we will create a new timestamp-value pair and append it to the corresponding key in the hashmap.

During get operation, we will take each pair corresponding to the key and traverse them to find the most significant pair that has a timestamp less than or equal to the required timestamp.

Below is the implementation of the TimeMap class:

class TimeMap {

Map<String, List<Pair<Integer, String>>> map;

/** Initialize your data structure here. */
public TimeMap() {
    map = new HashMap<>();
}

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

public String get(String key, int timestamp) {
    List<Pair<Integer, String>> list = map.get(key);
    if(list == null) {
        return "";
    }
    int left = 0;
    int right = list.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        Pair<Integer, String> pair = list.get(mid);
        if(pair.getKey() == timestamp) {
            return pair.getValue();
        }
        if(pair.getKey() < timestamp) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if(right < 0) {
        return "";
    }
    return list.get(right).getValue();
}

}

Complexity Analysis:

Time Complexity: The set operation will take O(1) time to insert a new key-value pair in the hashmap. The get operation will take O(logn) time to find the required value, where n is the total number of pairs corresponding to the key in the hashmap.

Space Complexity: The space required to store the hashmap will be O(nm), where n is the number of keys and m is the average number of pairs corresponding to each key.

1