[1146. Snapshot Array]

[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

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = -1
        self.collections = [[[self.snap_id, 0]] for _ in range(length)] 
        self.length = length
        
    def set(self, index: int, val: int) -> None:       
        if self.snap_id == self.collections[index][-1][0]:
            self.collections[index][-1][1] = val
        else:
            self.collections[index].append([self.snap_id, val])
        
    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id

    def get(self, index: int, snap_id: int) -> int:
        i = bisect.bisect_right(self.collections[index], [snap_id, float('-inf')]) - 1
        return self.collections[index][i][1]