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

For 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

What data structures and algorithms are best suited for this problem? What are the time and space complexities of each operation?

class SnapshotArray:

    def __init__(self, length: int):
        self.array = [[(0, 0)] for _ in range(length)]  # [(snap_id, val)]
        self.snap_id = 0

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

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

    def get(self, index: int, snap_id: int) -> int:
        arr = self.array[index]
        
        # Binary search for the largest snap_id <= target snap_id
        l, r = 0, len(arr) - 1
        ans = 0
        while l <= r:
            mid = (l + r) // 2
            if arr[mid][0] <= snap_id:
                ans = arr[mid][1]
                l = mid + 1
            else:
                r = mid - 1
        return ans


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

Explanation:

1. Initialization:

   • The __init__ method initializes the array as a list of lists. Each inner list represents an element of the snapshot array, and stores pairs of (snap_id, value). The initial value for each element is [(0, 0)], indicating that at snap_id = 0, the value is 0.
   • snap_id is initialized to 0, which is incremented each time snap() is called.

2. Set:

   • The set method appends a new (snap_id, val) pair to the inner list corresponding to the given index. This records the value val at the current snap_id.

3. Snap:

   • The snap method increments the snap_id and returns the previous snap_id.

4. Get:

   • The get method retrieves the value at the given index for the given snap_id.
   • It performs a binary search on the inner list at array[index] to find the largest snap_id that is less than or equal to the target snap_id.
   • The value associated with this snap_id is the value of the element at the time of the given snapshot.

Example:

snapshotArr = SnapshotArray(3);
snapshotArr.set(0,5);
snapshotArr.snap();  // Returns 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Returns 5

Time Complexity:

• SnapshotArray(length): O(length)
• set(index, val): O(1)
• snap(): O(1)
• get(index, snap_id): O(log n), where n is the number of times the element at index has been modified.

Space Complexity:

• SnapshotArray(length): O(length)
• The space complexity depends on the number of calls to set. In the worst case, if set is called for every element in the array for every snap, the space complexity can be O(length * number of snaps).