981. Time Based Key-Value Store

📝 Problem Details

• Title: 981. Time Based Key-Value Store
• Link: https://leetcode.com/problems/time-based-key-value-store/
• Difficulty: Medium
• Tags/Categories: Binary-Search Design Hashmap

💡 Explanation of Solution

- Hashmap (unordered_map) where:
	- Key --> string (key of the data store)
	- Value --> vector<pair<string, int>> a sorted list of values, stored with their timestamps

- Set Operation:
	- Directly push to the vector, since timestamps are montonically increasing (always added in order)

- Get Operation:
	- Binary search within the vector (since timestamps are sorted)

⌛ Complexity Analysis

Time Complexity:
	- set() is O(1) for appending a vector
	- get() is O(log N) binary search in a sorted list

Space Complexity: O(N) for storing all key-value+timestamp entries

💻 Implementation of Solution

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> store; // key -> [(timestamp, value)]
 
public:
    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value}); // Append since timestamps are increasing
    }
 
    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return ""; // Key doesn't exist
 
        auto& vec = store[key];
        int left = 0, right = vec.size() - 1;
        string res = "";
 
        // Binary search to find the largest timestamp <= target timestamp
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (vec[mid].first <= timestamp) {
                res = vec[mid].second; // Store potential result
                left = mid + 1; // Try to find a closer timestamp
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
};