981. Time Based Key-Value Store

 一刷 07/2022

Version #1 Binary Search

Time O(1) for set, O(logN) for get, N is the average number of values for each key

Space O(MN), N is the average number of values for each key, M is the number of keys

Runtime: 349 ms, faster than 31.75% of Java online submissions for Time Based Key-Value Store.

Memory Usage: 219.7 MB, less than 35.42% of Java online submissions for Time Based Key-Value Store.

class TimeMap {

    Map<String, List<Pair<Integer, String>>> map;

    public TimeMap() {

        map = new HashMap<>();

    }

    

    public void set(String key, String value, int timestamp) {

        map.putIfAbsent(key, new ArrayList<>());

        map.get(key).add(new Pair(timestamp, value));

    }

    

    public String get(String key, int timestamp) {

        if (!map.containsKey(key)) {

            return "";

        }

        List<Pair<Integer, String>> list = map.get(key);

        // find the largest timestamp that time <= given timestamp

        int start = 0, end = list.size() - 1;

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            Pair<Integer, String> midPair = list.get(mid);

            if (midPair.getKey() == timestamp) {

                return midPair.getValue();

            } else if (midPair.getKey() < timestamp) {

                start = mid;

            } else {

                end = mid - 1;

            }

        }

        if (list.get(end).getKey() <= timestamp) {

            return list.get(end).getValue();

        }

        if (list.get(start).getKey() <= timestamp) {

            return list.get(start).getValue();

        }

        return "";

    }

}

/**

 * Your TimeMap object will be instantiated and called as such:

 * TimeMap obj = new TimeMap();

 * obj.set(key,value,timestamp);

 * String param_2 = obj.get(key,timestamp);

 */