Grokking 233

class SnapshotArray {

    // Store the snapshots of each cell, not the whole array
    List<TreeMap<Integer, Integer>> arr;

    // Current snapshot number
    int current = 0;

    // We need to initialize the array length from the start
    public SnapshotArray(int length) {
        arr = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            arr.add(new TreeMap<Integer, Integer>());
            arr.get(i).put(0, 0);
        }
    }

    // Set the new value to the *current* snapshot of the cell at index *index*
    public void set(int index, int val) {
        arr.get(index).put(current, val);
    }

    public int snap() {
        return current++;
    }

    // In case number of "set" calls for a cell is less than total number of "snap" calls,
    // we have to get the "newest" snapshot available for that cell
    public int get(int index, int snap_id) {
        return arr.get(index).floorEntry(snap_id).getValue();
    }
}