# 1146 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
``````

Constraints:

• `1 <= length <= 5 * 104`
• `0 <= index < length`
• `0 <= val <= 109`
• `0 <= snap_id < `(the total number of times we call `snap()`)
• At most `5 * 104` calls will be made to `set`, `snap`, and `get`.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````class SnapshotArray: def __init__(self, length: int): ''' [ [[snap_id, val_0], ...] [[snap_id, val_1], ...] ] ''' self.array = [[[-1, 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: idx = bisect.bisect(self.array[index], [snap_id+1]) - 1 return self.array[index][idx][1] # 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)``````