1
# Runtime: 600 ms (Top 65.10%) | Memory: 33.5 MB (Top 72.09%)
2
class SnapshotArray:
3

4
    def __init__(self, length: int):
5
        self.snap_id = 0
6
        self.history = defaultdict(dict)
7

8
    def set(self, index: int, val: int) -> None:
9
        self.history[self.snap_id][index] = val
10

11
    def snap(self) -> int:
12
        self.snap_id += 1
13
        return self.snap_id - 1
14

15
    def get(self, index: int, snap_id: int) -> int:
16
        for i in range(snap_id, -1, -1):
17
            if index in self.history[i]:
18
                return self.history[i][index]
19
        return 0  # default value in case it wasn't set earlier