Snapshot Array

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

---

A brute force approach would be to utilize a HashMap and hash each snap with a copy of the array in its current state during each time the snap function was called.  If the get function was then called, we would be able to grab the appropriate array through the input snap key, then return the input index.

However, there are two things we may notice.

1. We are only updating one index at a time through a set function call.

2. Each snap is given in strictly non-decreasing order.

 

Due to the first realization, each time we make a copy of the array to map within the HashMap, we may find that we are copying and updating an entire array when we only need to change a single index.  We are forcing an O(N) operation when an O(1) operation will do.

Due to the second realization, we are given an easily searchable structure since whatever updates we make will be in essentially sorted order.

Now we may find a better approach.

What we can do instead is hash indices with the updates that were set.  After we do that, when the get method is called, we can search for the respective snap by performing a binary search.  This is similar to the question Time Based Key-Value Store.

---

 Let's start by initializing our data structure and our snaps.

    def __init__(self, length: int):

 

We could choose to hash the indices in a HashMap, but since the problem description asks for an array-like data structure, let's just use a matrix instead.  With the matrix, each column will be a mapping of the set updates to the respective index.

If we look at the first example, the Snapshot Array would look like this.

(0,0)	(0,0)	(0,0)
(0,5)
(1,6)

 

The problem description says that each index is initialized with a value of zero, with zero snaps.

        self.array = [[(0, 0)] for index in range(length)]
        self.snaps = 0

---

Next, we'll make our set function which will append the snap id and the value to the appropriate index column within the matrix.

    def set(self, index: int, val: int) -> None:
        self.array[index].append((self.snaps, val))

---

Next, we'll make our snap function which will increment the number of snaps that have been called then return that number minus one, according to the problem description.

    def snap(self) -> int:
        self.snaps += 1
        return self.snaps - 1

---

Lastly, we'll make our get method.

    def get(self, index: int, snap_id: int) -> int:

 

The snapshots of the given index that we'll be performing a binary search on will be the corresponding index column from our matrix.

        index_snaps = self.array[index]

 

We'll set our pointers and begin.

        left, right = 0, len(index_snaps) - 1

 

While our pointers haven't crossed each other, we will continue our search.

        while left <= right:

 

Let's set the middle pointer to the mean of our two pointers.

            mid = (left + right) // 2

 

This isn't mentioned in the problem description, but we are going to have duplicate snap IDs and we're going to want to return the last index value of the given snap ID.

That means if we come across the index with the given snap ID, we aren't going to be able to terminate our search, we will have to exhaust our entire search space to find the last index update of the given snap ID.

If the current middle snap is less than or equal to the input snap ID, we'll abandon our left partition and keep looking for the final update.

            if index_snaps[mid][0] <= snap_id:
                left = mid + 1

 

Otherwise, we'll abandon our right partition instead.

            else:
                right = mid - 1

 

Once our pointers have overlapped, that would mean two things; either the left pointer passed the last snap less than or equal to the target or the right pointer passed the last snap greater than the target.

In either scenario, the target would be one index behind the left pointer which would be where the right pointer ended up at.

We'll return that value.

        return index_snaps[right][1]

---