042_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

C++

class SnapshotArray {
public:
    vector<unordered_map<int, int>> arr;
    int snapId;
    SnapshotArray(int length) {
        arr.resize(length);
        snapId = 0;
    }
    
    void set(int index, int val) {
        arr[index][snapId] = val;
    }
    
    int snap() {
        return snapId++;
    }
    
    int get(int index, int snap_id) {
        while(snap_id >= 0 && arr[index].find(snap_id) == arr[index].end()){
            snap_id--;
        }

        if(snap_id < 0){
            return 0;
        }
        return arr[index][snap_id];
    }
};

/**
 * 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);
 */