Grokking 233

class SnapshotArray {

    // 0-indexed list of snapshots. Each snapshot is a hashtable (i.e. a HashMap in Java).
    List<Map<Integer, Integer>> snapshots = new ArrayList<>();
    Map<Integer, Integer> current = new HashMap<>();

    // Since Java Collection data structures dynamically allocate their size, we don't need to handle array maximum length.
    public SnapshotArray(int length) { }

    // New data will be set as a Key-Value entry to the current snapshot.
    public void set(int index, int val) {
        current.put(index, val);
    }

    // Each new snapshot is a copy of the previous hashtable.
    public int snap() {
        snapshots.add(new HashMap<>(current));
        current = new HashMap<>(current);
        return snapshots.size() - 1;
    }

    public int get(int index, int snap_id) {
        Integer val = snapshots.get(snap_id).get(index);
        return val == null ? 0 : val;
    }
}