1146. Snapshot Array - cocoder39/coco39_LC GitHub Wiki

1146. Snapshot Array

Option 1: hash map

class SnapshotArray:

    def __init__(self, length: int):
        self.snapId = 0
        self.snaps = collections.defaultdict(dict)

    def set(self, index: int, val: int) -> None:
        self.snaps[index][self.snapId] = val

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

    def get(self, index: int, snap_id: int) -> int:
        while snap_id > 0 and snap_id not in self.snaps[index]:
            snap_id -= 1
        
        if snap_id in self.snaps[index]:
            return self.snaps[index][snap_id]
        return 0

Option 2: binary search

class SnapshotArray:

    def __init__(self, length: int):
        self.snapId = 0
        self.snaps = [[] for i in range(length)]

    def set(self, index: int, val: int) -> None:
        if not self.snaps[index] or self.snapId > self.snaps[index][-1][0]:
            self.snaps[index].append([self.snapId, val])
        else:
            self.snaps[index][-1] = [self.snapId, val]

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

    def get(self, index: int, snap_id: int) -> int:
        idx = bisect.bisect_right(self.snaps[index], [snap_id+1]) - 1
        return self.snaps[index][idx][1] if idx >= 0 else 0