3. 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

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Solution: (Binary Search)

Approach: Instead of copy the whole array, we can only record the changes of the index

class SnapshotArray
{
public:
    unordered_map<int, map<int, int>> m;
    int snapId;

    SnapshotArray(int length)
    {
        snapId = 0;
        for (int i = 0; i < length; i++)
        {
            map<int, int> sp;
            sp[0] = 0;
            m[i] = sp;
        }
    }

    void set(int index, int val)
    {
        m[index][snapId] = val;
    }

    int snap()
    {
        return snapId++;
    }

    int get(int index, int snap_id)
    {
        auto itr = m[index].lower_bound(snap_id);
        
        if (itr == m[index].end() || itr->first!=snap_id) 
        {
            itr--;
            return itr->second;
        }
        
        return itr->second;
    }
};

Time Complexity: SnapshotArray(int length) is O(N) time set(int index, int val) is O(log snap) snap() is O(1) get(int index, int snap_id) is O(log Snap)