Sponsored
Sponsored
This approach uses a HashMap where each key points to a sorted list of timestamp-value pairs. The 'set' function appends the value along with the timestamp to the list associated with the key. The 'get' function retrieves the value at a particular timestamp by performing a binary search to find the rightmost timestamp less than or equal to the requested timestamp.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.
1class TimeMap {
2 constructor() {
3 this.store = new Map();
4 }
5 set(key, value, timestamp) {
6 if (!this.store.has(key)) {
7 this.store.set(key, []);
8 }
9 this.store.get(key).push({ timestamp, value });
10 }
11 get(key, timestamp) {
12 if (!this.store.has(key)) return "";
13 let values = this.store.get(key);
14 let left = 0, right = values.length - 1;
15 while (left <= right) {
16 const mid = Math.floor((left + right) / 2);
17 if (values[mid].timestamp <= timestamp) {
18 left = mid + 1;
19 } else {
20 right = mid - 1;
21 }
22 }
23 return right >= 0 ? values[right].value : "";
24 }
25}The JavaScript solution uses a Map data structure to store timestamps and values. The 'set' method appends each timestamp-value pair to an array. The 'get' function performs a binary search on this array to find the largest timestamp less than or equal to the given timestamp, ensuring a logarithmic time complexity for retrieval.
This approach is similar, but instead of using a helper library for the binary search, we implement it manually. This approach provides more control over the binary search process.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.
1import java.util.*;
2In Java, we utilize a HashMap to store a List of Pair objects for each key. Each Pair object contains a timestamp and its corresponding value. For retrieval, we perform manual binary search logic to find the appropriate timestamp efficiently in logarithmic time.