The naive approach which comes to mind is to have a 2D array where snapshot[i] saves the i-th snapshot, i.e., an array of size length. It is easy to identify that this approach can be really slow if there are frequent calls to the snap() function and only very little changes between two snaps as we’ll have to copy lots of elements to the new array which haven’t even changes since long. Let’s consider an alternative approach:
The idea is to maintain a 2D map unordered_map<int, unordered_map<int, int>> map where map[i][snap] stores the value of element at index i in the array for each snapshot snap. Now, suppose the initial value for index 2 is 0. Then map[2][0] = 0. Then, it only changes its value to 5 in the third snapshot making map[2][3] = 5. Note that we are not storing value for index 2 for the snapshots 1 and 2. This saves us a lot of space. This insertion time is O(1).
Now, to find the value of index i at snapshot j, we just have to iterate over map[i] and find its value for an index equal to or just below j. Note that this may take O(n) time where n is the number of snaps.
At the cost of insertion, we can bring the time of getting value of index i at snapshot to O(logn) from O(n). This can be particularly useful if the function get is called a lot more than the function set. The idea is to use an ordered map insider: unordered_map<int, map<int, int>> m. This way instead of linearly searching for the index j as above, we can use binary search. The following code implements this idea and uses the STL algorithm upper_bound which is implemented using binary search internally:
class SnapshotArray {
public:
unordered_map<int, map<int,int>> m;
int currSnap = 0;
SnapshotArray(int length) {
}
void set(int index, int val) {
m[index][currSnap] = val;
}
int snap() {
return currSnap++;
}
int get(int index, int snap_id) {
auto it = m[index].upper_bound(snap_id);
return it == begin(m[index]) ? 0 : prev(it)->second;
}
};
Time complexities:
set: O(logn) where n is the number of snapshots
snap: O(1)
get: O(logn) where n is the number of snapshots