Solution


Intuition and Algorithm

For each key we get or set, we only care about the timestamps and values for that key. We can store this information in a HashMap.

Now, for each key, we can binary search the sorted list of timestamps to find the relevant value for that key.

Complexity Analysis

  • Time Complexity: for each set operation, and for each get operation, where is the number of entries in the TimeMap.

  • Space Complexity: .


Approach 2: TreeMap

Intuition and Algorithm

In Java, we can use TreeMap.floorKey(timestamp) to find the largest timestamp smaller than the given timestamp.

We build our solution in the same way as Approach 1, swapping in this functionality.

Complexity Analysis

  • Time Complexity: for each set operation, and for each get operation, where is the number of entries in the TimeMap.

  • Space Complexity: .


Analysis written by: @awice.