[Leetcode 1146] Snapshot Array

 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

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

Analysis:

This question is designed for data structure.

The snap_id is increased one by one, which means we can use a vector to record the snap information. The id of the vector becomes the snap_id naturally;

The length could be very large, like 50000, so if we use a something with similar sizes, it would be too large. Instead, we just need to record the elements that are updated (or set with values). One solution can use a unordered_map for this. The key will be the data index, and the value is the data value to be set.

Thus, the overall data structure is vector<unordered_map<int, int>>.

See the code below:

class SnapshotArray {
public:
    SnapshotArray(int length) {
        vmps.resize(1);
    }
    
    void set(int index, int val) {
        // assume index and snap_id are always valid
        vmps[id][index] = val;
    }
    
    int snap() {
        vmps.push_back(vmps[id]);
        return id++;
    }
    
    int get(int index, int snap_id) {
        // assume index and snap_id are always valid
        return vmps[snap_id][index];
    }
private:
    int id = 0;
    vector<unordered_map<int, int>> vmps;
};

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