Time Based Key-Value Store

Problem Statement

LeetCode-981: Design a time-based key-value store 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 one with the largest timestamp_prev. If there are no values, it returns "".

Approach

As mentioned in the constraints, all the timestamps timestamp of set are strictly increasing. This means that if we store the timestamps in a list, the list will always be sorted in ascending order of timestamp.

This will help us in performing binary search to find the value for a given key at a given timestamp. The hihg-level approach is as follows:

• We will store the values for a given key in a list.
• The list will be sorted in ascending order of timestamp.
• To find the value for a given key at a given timestamp, we will perform binary search on the list of values for the given key.
• If the timestamp is present in the list, we will return the value at that timestamp.
• If the timestamp is not present in the list, we will return the value at the floor timestamp.
• The floor timestamp is the largest timestamp that is just less than the given timestamp.

Implementation

// a DS to store the value at given timestamp
private record Pair(String value, int time){}
private final Map<String, List<Pair>> entries;

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

// store the value(s) at given timestamp(s) for a given key
public void set(String key, String value, int timestamp) {
    List<Pair> vals = entries.getOrDefault(key, new ArrayList<>());
    vals.add(new Pair(value, timestamp));
    entries.put(key, vals);    
}

// get the value for a given key at a given timestamp
public String get(String key, int timestamp) {
    if(entries.containsKey(key)){
        List<Pair> vals = entries.get(key);
        Pair val = floor(vals, timestamp);
        return null == val ? "" : val.value;
    }
    return "";
}

// find the value for a given key at a given timestamp
// if the timestamp is not present, return the value at the floor timestamp
// using binary search
private Pair floor(List<Pair>vals, int time){
    int start = 0;
    int end = vals.size()-1;
    
    Pair ans = null;
    while(start <= end){
        int mid = start + (end-start)/2;
        if(vals.get(mid).time == time){
            ans = vals.get(mid);
            break;
        }else if(vals.get(mid).time > time){
            end = mid-1;
        }else{
            start = mid+1;
            ans = vals.get(mid);
        }
        
    }
    return ans;
}

Complexity Analysis

• The time complexity for the set operation is $O(1)$ as we are just adding the value to the list of values for a given key.
• The time complexity for the get operation is $O(\log n)$ where $n$ is the number of values stored for a given key. This is because we are performing binary search to find the value for a given timestamp.