Question

Code

class SnapshotArray:

    def __init__(self, length: int):
        self.id = 0
        self.history_records = [[[0, 0]] for _ in range(length)]

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

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

    def get(self, index: int, snap_id: int) -> int:
        arr = self.history_records[index]

        l, r = 0, len(arr) - 1


        while l <= r:
            m = l + (r - l) // 2
            
            curId, curVal = arr[m]
            
            if curId > snap_id:
                r = m - 1
            else:
                if m == len(arr) - 1 or arr[m + 1][0] > snap_id:
                    return arr[m][1]
                else:
                    l = m + 1

        return 0

        
# 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)