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:

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.

class SnapshotArray:

    def __init__(self, length: int):
        self.array = [[(0, 0)] for _ in range(length)]
        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 to find the largest snap_id <= given 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 stores the history of changes for a specific index. Each element in the inner list is a tuple (snap_id, value). It also initializes snap_id to 0.

2. Set:

   • The set method appends the current snap_id and the new val to the history list of the given index.

3. Snap:

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

4. Get:

   • The get method performs a binary search on the history list of the given index to find the value associated with the largest snap_id that is less than or equal to the given snap_id. This ensures that we retrieve the most recent value at or before the specified snapshot.

Time and Space Complexity:

• Time Complexity:
  • SnapshotArray: O(length)
  • set: O(1)
  • snap: O(1)
  • get: O(log K), where K is the number of times set was called on that index.
• Space Complexity: O(N * M), where N is the length of the array and M is the number of times set is called.