[LeetCode] Snapshot Array

Problem: 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:

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

Constraints:

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < (the total number of times we call snap())
• At most 5 * 10^4 calls will be made to set, snap, and get.

Approach: First thing in the problem we can notice that we can't save full array, every time we take the snapshot as the length of the array could be 5 * 10 ^ 4 and snap can be called 5 * 10 ^ 4 times.

What we can do is we only store the updates which happened in the current snapshot. In this way for every index we will have a list of snapshot id and the value updates so now when we try to get the value given the snapshot we can do following:

• If no modification i.e. list of updates at the input index will be  null or if no snapshot is taken i.e. current snapshot id is still 0 then we can simply return 0.
• Else we find the upper bound of snap_id using binary search and return the stored value.

That's all!

Implementation in C#:

public class SnapshotArray

{

    public SnapshotArray(int length)

    {

        this.snapshots = new List<Tuple<int, int>>[length];

        this.currSnapId = 0;

    }

   

    public void Set(int index, int val)

    {

        if (this.snapshots[index] == null)

        {

            this.snapshots[index] = new List<Tuple<int, int>>();

        }

        int length = this.snapshots[index].Count;

        if (length > 0 &&

            this.snapshots[index][length - 1].Item1 == this.currSnapId)

        {

            this.snapshots[index].RemoveAt(length - 1);

        }

        this.snapshots[index].Add(new Tuple<int, int>(this.currSnapId,

                                                      val));

    }

   

    public int Snap()

    {

        ++this.currSnapId;

        return this.currSnapId - 1;

    }

   

    public int Get(int index, int snap_id)

    {

        // No modification or no snapshot taken

        if (this.snapshots[index] == null || this.currSnapId == 0)

        {

            return 0;

        }

        int snapIndex = this.FindSnapIndex(this.snapshots[index], snap_id);

        return snapIndex == -1 ?

               0 :

               this.snapshots[index][snapIndex].Item2;

    }

    private int FindSnapIndex(List<Tuple<int, int>> snapIds, int snapId)

    {

        int start = 0, end = snapIds.Count - 1;

        if (snapId >= snapIds[end].Item1)

        {

            return end;

        }

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            int currSnap = snapIds[mid].Item1;

            if (currSnap == snapId)

            {

                return mid;

            }

            else if (currSnap < snapId)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return end;

    }

    private List<Tuple<int, int>>[] snapshots;

    private int currSnapId;

}

Complexity: SnapshotArray: O(1), Set: O(1), Snap: O(1), Get: O(logn)