LeetCode 981: Time Based Key-Value Store Solution

Master LeetCode problem 981 (Time Based Key-Value Store), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

981. Time Based Key-Value Store

Medium

Hash Table String Binary Search Design

Problem Explanation

Explanation:

To solve this problem, we can use a HashMap to store the key-value pairs where the value is a TreeMap. The TreeMap will store the timestamps as keys and values as the corresponding values at those timestamps. When we want to retrieve a value for a given key and timestamp, we can perform a binary search in the TreeMap to find the largest timestamp less than or equal to the given timestamp.

Time Complexity Analysis:
- The time complexity for the set operation is O(logN) where N is the number of timestamps for a specific key in the TreeMap.
- The time complexity for the get operation is O(logN) where N is the number of timestamps for a specific key in the TreeMap.
Space Complexity:
- The space complexity is O(N) where N is the total number of unique key-timestamp pairs stored.

Solution Code

import java.util.*;

class TimeMap {
    Map<String, TreeMap<Integer, String>> map;

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

    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new TreeMap<>());
        map.get(key).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> treeMap = map.get(key);
        if (treeMap == null) return "";
        
        Integer floorKey = treeMap.floorKey(timestamp);
        return floorKey != null ? treeMap.get(floorKey) : "";
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 981 (Time Based Key-Value Store)?

This page provides optimized solutions for LeetCode problem 981 (Time Based Key-Value Store) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 981 (Time Based Key-Value Store)?

The time complexity for LeetCode 981 (Time Based Key-Value Store) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 981 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 981 in Java, C++, or Python.

Back to LeetCode Solutions