1146. Snapshot Array

Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.

• void set(index, val) sets the element at the given index to be equal to val.

• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.

• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

• 1 <= length <= 50000

• At most 50000 calls will be made to set, snap, and get.

• 0 <= index < length

• 0 <= snap_id < (the total number of times we call snap())

• 0 <= val <= 10^9

Solution

The first idea is to use Array and List to record all the snapshots and its array. It is not ok, because of using too much memory.

The second one is to use two Maps, one is dataMap to record value and index, another is to record the mapping between the snapshot id and dataMap. It works but it is not good enough.

After reading the discussion, we can do it with TreeMap, and take the advantage of floorKey(). It can help us to find the closest snapshot. We just keep updating the changed value and its snapshotID in the TreeMap. And we can get the closest one to the given snapshot by floorKey().

class SnapshotArray {
    TreeMap<Integer, Integer>[] map;
    int lastSnapId = 0;
    public SnapshotArray(int length) {
        map = new TreeMap[length];
        for(int i = 0; i < length; i++){
            map[i] = new TreeMap<Integer, Integer>();
        }
    }
    
    public void set(int index, int val) {
        map[index].put(lastSnapId, val);
    }
    
    public int snap() {
        return lastSnapId++;
    }
    
    public int get(int index, int snap_id) {
        Integer key = map[index].floorKey(snap_id);
        return key == null ? 0 : map[index].get(key);
    }
}