Problem statement

https://binarysearch.com/problems/Snapshottable-List/

Solution

Equal to Leetcode 1146 Snapshot Array.

Complexity

See complexities of leetcode problem.

Code

class SnapshottableList:
    def __init__(self, length):
        self.snap_id = 0
        self.array = [[(-1,0)] for _ in range(length)] 

    def set(self, index, val):
        self.array[index] += [(self.snap_id, val)]
        
    def snapshot(self):
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index, snap_id):
        ind = bisect.bisect(self.array[index], (snap_id, float("inf"))) - 1
        return self.array[index][ind][1]