981. Time Based Key-Value Store

First solution -> HashMap + list time complexity of set() ---- O(1) best case, O(n) worst case, because ArrayList needs to be rearranged in case internal array is overflowed. time complexity of get() ---- O(log n) since we perform binary search

Second solution -> HashMap + TreeMap time complexity of set() ---- O(log k) , because we're updating a TreeMap with k number of timestamps. time complexity of get() ---- O(log n) , because tree map internally uses binary search tree for sorting out the elements.

ask timestamp is ordered, increasing?

1. for the question, so we want the value ( timestamp <= query input's timestamp, closest one)

so can leverage treemap's floorKey() (treeMap<timestmap, value> or

2. use BS to find the closest value (timestamp <= query input's timestamp)

HashMap + list , Binary search (append to list set() is better! O(1))

from constraint:

• All the timestamps timestamp of set are strictly increasing.

so in actually, we can use bs in List

    protected String binarySearch(List<Data> list, int time) {
        int low = 0, high = list.size() - 1;
        while (low +1 < high) {
            int mid = (low + high) >> 1;
            if (list.get(mid).time <= time) {
                low = mid;
            } else {
                high = mid;
            }
        }
        // we want closest time, so compare end first
        if (list.get(high).time <= time) {
            return list.get(high).val;
        }
        if (list.get(low).time <= time) {
            return list.get(low).val;
        }
        return "";
    }

T: set: O(1), get: O(1) + O(logn), n is list len

S: O(m*n), m - hashmap size, n - each list size

class TimeMap {

    class Data {
        String value;
        int time;
        Data(String value, int time) {
            this.value = value;
            this.time = time;
        }
    }

    Map<String, List<Data>> map;
    public TimeMap() {
        this.map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>());
        map.get(key).add(new Data(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        return binarySearch(map.get(key), timestamp);
    }

    private String binarySearch(List<Data> list, int timestamp) {
        int start = 0;
        int end = list.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (list.get(mid).time <= timestamp) {
                start = mid;
            } else {
                end = mid;
            }
        }
        // we want closest time, so compare end first
        if (list.get(end).time <= timestamp) {
            return list.get(end).value;
        }
        if (list.get(start).time <= timestamp) {
            return list.get(start).value;
        }
        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);
 */

HashMap + TreeMap

T: set: O(logn), get: O(1) + O(logn), n is treemap size

S: O(m*n), m - hashmap size, n - each treemap size

floorKey()-> the first greatest number <= given key;
ceillingKey()_> the first smaller number >=given key;


String get(String key, int timestamp) 
Returns a value such that set was called previously, 
with timestamp_prev <= timestamp. (so use floorKey)

class TimeMap {
    Map<String, TreeMap<Integer, String>> map;
    public TimeMap() {
        this.map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, m -> new TreeMap<>());
        map.get(key).put(timestamp, value);
    }
    
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> data = map.get(key);
        if (data == null) {
            return "";
        }
        Integer floor = data.floorKey(timestamp);
        if (floor == null) {
            return "";
        }
        return data.get(floor);
    }
}