23.06.11 Today’s Leetcode

1146. Snapshot Array (medium)

with Array

class SnapshotArray:

    def __init__(self, length: int):
        self.d = [0] * length
        self.len = length
        self.snapshots = {}
        self.cur_id = 0

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

    def snap(self) -> int:
        self.snapshots[self.cur_id] = self.d[:]
        self.cur_id += 1
        return self.cur_id - 1
        
    def get(self, index: int, snap_id: int) -> int:
        return self.snapshots[snap_id][index]

with Saving Changed Data

class SnapshotArray:

    def __init__(self, length: int):
        self.d = [0] * length
        self.len = length
        self.snapshots = []
        self.cur_changed = set()
        self.cur_id = 0

    def set(self, index: int, val: int) -> None:
        self.d[index] = val
        self.cur_changed.add((index, val))

    def snap(self) -> int:
        self.snapshots.append(self.cur_changed)
        self.cur_changed = set()
        self.cur_id += 1
        return self.cur_id - 1
        
    def get(self, index: int, snap_id: int) -> int:
        for i in range(snap_id, -1, -1):
            changes = self.snapshots[i]
            for temp in changes:
                if temp[0] == index:
                    return temp[1]
        return 0

Solution

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

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

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

    def get(self, index: int, snap_id: int) -> int:
        history = self.array[index]
        left, right = 0, len(history) - 1

        while left <= right:
            mid = (left + right) // 2
            if history[mid][0] <= snap_id:
                left = mid + 1
            else:
                right = mid - 1

        return history[right][1]