1146. Snapshot Array

T: 
set, get: O(logn), n is set times
snap():O(1)

S: O(length*n), length is input size, n is set times

class SnapshotArray {
    TreeMap<Integer, Integer>[] map;
    int snapId = 0;
    public SnapshotArray(int length) {
        map = new TreeMap[length];
        for (int i = 0; i < length;i++) {
            map[i] = new TreeMap<>();
            map[i].put(0, 0);
        }
    }
    
    public void set(int index, int val) { // set index, val to tree map
        map[index].put(snapId, val);
    }
    
    public int snap() { // when do snap, increase snapId
        return snapId++;
    }
    // because snapshot maybe like : 
    // map[index]: (snapId, value) => index = 0, map[0] : (1,3)  (5,6), 
    // when we want index = 0, snapId = 4, find snapId <= 4, so find (1,3) => value = 3
    // floorEntry(key), get <= key's closet key
    public int get(int index, int snap_id) {
        return map[index].floorEntry(snap_id).getValue();
    }
}

/**
1.
naive:
1 <= length <= 50000
snapshot entire array
so
array*snapshot = 50000*50000 => waste spaces

2.
use treeMap:

only record snapshot data in List<treeMap>
list[index].treeMap
for each index, save sanpId, value in treeMap

for get treeMap, it can use floorEntry(snap_id), find closet <= key's key

T: 
set, get: O(logn), n is set times
snap():O(1)

S: O(length*n), length is input size, n is set times

 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

use floorKey()

class SnapshotArray {

    int snapId = 0;
    TreeMap<Integer, Integer>[] map;
    
    public SnapshotArray(int length) {
        map = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            map[i] = new TreeMap<>();
            map[i].put(0, 0);
        }
    }
    
    // compare to save this index's all data, we only record change part(snapId, val)
    /*
        set(index, val), 
        set(0,5)
        set(0,6)
        snap => snapId: 0:  (0, 5),(0, 6)
        set(0,8)
        snap => snapId: 1:  (0, 5),(0, 6),(0,8)
        
        only record change part(snapId, val):
        index: 0 -> (snapId, val), (0, 6), (1, 8)
    */
    public void set(int index, int val) {
        map[index].put(snapId, val); 
    }
    
    public int snap() {
        snapId++;
        return snapId-1;
    }
    
    public int get(int index, int snap_id) {
        Integer closestKey = map[index].floorKey(snap_id);
        return map[index].get(closestKey);
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

why don't need check null in last step?

public int get(int index, int snap_id) {
        TreeMap<Integer, Integer> map = mapArray[index];
        if (map == null) {
            return 0;
        }
        Integer floorKey = map.floorKey(snap_id);
        if (floorKey == null) {
            return 0;
        }
        return map.get(floorKey);
    }

because question mentioned about